Bacterial infections are common complications of solid organ transplantation (SOT). In this study, we defined the incidence, mortality and in vitro antimicrobial resistance rates of Gram-negative bloodstream infection (BSI) in SOT recipients. We identified 223 patients who developed Gram-negative BSI among a cohort of 3367 SOT recipients who were prospectively followed at the Mayo Clinic (Rochester, MN) from January 1, 1996 to December 31, 2007. The highest incidence rate (IR) of Gram-negative BSI was observed within the first month following SOT (210.3/1000 person-years [95% confidence interval (CI): 159.3-268.3]), with a sharp decline to 25.7 (95% CI: 20.1-32.1) and 8.2 (95% CI: 6.7-10.0) per 1000 person-years between 2 and 12 months and more than 12 months following SOT, respectively. Kidney recipients were more likely to develop Gram-negative BSI after 12 months following transplantation than were liver recipients (10.3 [95% CI: 7.9-13.1] vs. 5.2 [95% CI: 3.1-7.8] per 1000 person-years). The overall unadjusted 28-day all-cause mortality of Gram-negative BSI was 4.9% and was lower in kidney than in liver recipients (1.6% vs. 13.2%, p < 0.001). We observed a linear trend of increasing resistance among Escherichia coli isolates to fluoroquinolone antibiotics from 0% to 44% (p = 0.002) throughout the study period. This increase in antimicrobial resistance may influence the choice of empiric therapy.