Infectious proctitis is usually associated with sexually transmitted diseases, especially in HIV-infected individuals. Limited information is found about the role of Mycobacterium avium-intracellulare as a causative agent for this condition. Here, we report the case of an HIV-infected patient with a CD4 count of 304 cells/uL and undetectable HIV viral load, who presented with constipation and painful defecation. Endoscopic evaluation was significant for shallow rectal ulcerations. Histopathology revealed poorly formed granulomas. Stool culture grew Mycobacterium sp. that was further identified as Mycobacterium avium-intracellulare by DNA probe. He was successfully treated with a 3-drug regimen that included azithromycin, ethambutol and rifabutin. We advocate the use of AFB stool culture in cases of proctitis in which initial investigations for sexually transmitted diseases are unrevealing.