Group IV atypical mycobacterial infections, especially Mycobacterium fortuitum and M. chelonei, are being reported with increased frequency. We report our experience with five cases of soft-tissue infection with these acid-fast bacilli. Often these infections are chronic, with formation of abscesses and multiple fistulas. Optimal surgical treatment often requires wide excision of all diseased tissue followed by delayed closure. Presentation, optimal surgical management, and antibiotic therapy are discussed.