Inadequate empirical antibiotic therapy for serious Pseudomonas aeruginosa infections has been linked to increased mortality. We performed a retrospective cohort study of consecutive patients with ventilator-associated pneumonia, bacteraemia or other sterile-site infections caused by P. aeruginosa occurring during Intensive Care Unit admissions. One hundred and fifty-eight episodes of serious infection with P. aeruginosa occurred in 140 patients. Empirical antibiotic therapy was microbiologically adequate in 67% of episodes of infection. Patients with P. aeruginosa isolates resistant to piperacillin/tazobactam or cefepime were more likely to have received these antibiotics in the month prior to the P. aeruginosa infection or to have had a Gram-negative bacillus resistant to these antibiotics isolated in the month prior to the P. aeruginosa infection. From these data, we have developed simple algorithms for empirical antibiotic choice in seriously ill patients with suspected P. aeruginosa infections based on prior antibiotic exposure and prior isolation of antibiotic-resistant organisms. Application of these algorithms would have improved the adequacy of empirical antibiotic therapy from 67% to 80-84%. Routine empirical addition of amikacin to the beta-lactam would have increased the adequacy of the antibiotics to 96%. We conclude that knowledge of the prior receipt of beta-lactam antibiotics with activity against P. aeruginosa and the isolation of Gram-negative bacilli resistant to such antibiotics in the recent past can readily increase the adequacy of empirical antibiotic therapy for suspected P. aeruginosa infections.