Sphingomonas paucimobilis is an aerobic gram-negative bacillus that causes a variety of infections in healthy as well as in immunocompromised individuals. The organism is usually susceptible to tetracycline, chloramphenicol, aminoglycosides, trimethoprim-sulfamethoxazole, and carbapenems. However, resistance to penicillins and the first-generation cephalosporins is commonly encountered. Reported here is a patient with acute myeloid leukemia who developed S. paucimobilis bacteremia complicated by septic shock just before receiving an autologous hematopoietic stem cell transplant (SCT) at King Faisal Specialist Hospital and Research Centre in Riyadh. The septic episode was successfully treated in the intensive care unit. To our knowledge, this is the first case report of septic shock caused by S. paucimobilis bacteremia in a hematopoietic SCT recipient.