Acid-fast bacillus (AFB) spinal osteomyelitis in a patient with AIDS is often presumed to be caused by reactivated Mycobacterium tuberculosis. However, other AFB pathogens can mimic M. tuberculosis and, to ensure appropriate and adequate therapy, should be considered by clinicians. We present a case of aggressive spinal osteomyelitis caused by Mycobacterium heckeshornense in an AIDS patient; a review of the literature is also included.