We describe the first Mycobacterium haemophilum infection that occurred in a patient with human immunodeficiency virus in Germany and report 7 newly diagnosed cases of M. haemophilum infection. In the former case, a local M. haemophilum skin infection resolved as a result of successful antiretroviral therapy only; however, that clinical outcome may not be possible for more invasive forms of the disease.