Mycobacterium haemophilum is a nontuberculous mycobacteria (NTM) with a predilection for skin and soft tissue infection (SSTI) in the immunocompromised host. We report a case of disseminated M haemophilum infection initially presenting as a nonresolving subacute cellulitis of bilateral lower extremities. Genetic sequencing was used for final identification, while a commercially available polymerase chain reaction test returned a false-positive result for Mycobacterium intracellulare. Consequently, we highlight the importance of M haemophilum as a major differential diagnosis of SSTI in the immunocompromised host and the need for careful interpretation of rapid diagnostic tests.