Non-tuberculous mycobacteria (NTM) are ubiquitous organisms, of which some, especially those of the Mycobacterium avium complex (MAC), may be opportunistic animal and human pathogens. Infection with NTM can interfere with tuberculosis (TB) diagnosis and induce zoonoses, especially in immunocompromised individuals. Diseases caused by NTM have become more readily recognized; however, they are likely still underestimated. In this study, we identified and genotyped Mycobacterium avium strains that were isolated during TB monitoring among free-living carnivorous animals from southeastern Poland. In 2011–2020, lymph node samples from 192 such animals were tested for mycobacteria. A total of 41 isolates of M. avium strains were detected with the use of IS901, IS900, IS1245, and mycobacterial interspersed repeat unit–variable number tandem repeat (MIRU-VNTR) identification. Thirty-three were identified as M. avium subsp. avium. These strains were derived from 1 beech marten (Martes foina), 1 common buzzard (Buteo buteo), 2 European badgers (Meles meles), 3 wolves (Canis lupus), and 26 red foxes (Vulpes vulpes). One strain isolated from a wolf was identified as M. avium subsp. hominissuis. The results show the widespread occurrence of MAC bacilli in the studied environment and additionally comprise new data on the molecular characteristics of M. avium subspecies carried by free-living southeastern Polish carnivores.