Mycobacterium avium subsp. paratuberculosis (MAP), the causative agent of Johne disease in ruminants, has been incriminated as the cause of Crohn disease in humans. We report the first case of human infection with MAP in a patient with HIV; infection was confirmed by obtaining isolates from several different specimen types.