Mycobacterium szulgai is a scotochromogen mycobacterium that accounts for < 1% of all human isolates of non-tuberculous mycobacteria. We report the first case of osteomyelitis caused by Mycobacterium szulgai in an AIDS patient. Culture from tissue was needed for isolation and identification of the organism, which was initially misidentified as Mycobacterium gordonae. Susceptibility testing to a fluoroquinolone was carried out and is also reported here for the first time. This case demonstrates the pathogenic potential of M. szulgai in this setting, and illustrates the need to obtain tissue specimens for culture in infected immunosuppressed patients to make a specific microbiological diagnosis and institute appropriate therapy.