Pyomyositis due to Gram negative bacteria is rare. Here we describe two cases in immunocompromised hosts. Both were bacteremic with a Gram-negative bacterium and had impaired immunity related to prolonged and ongoing chemotherapy for hematologic malignancies. Both eventually cleared the infection with a combination of local drainage and systemic antibiotics. This unusual diagnosis should be considered in an immunocompromised patient with muscle pain and fever.