Enterocytozoon bieneusi is a common intracellular parasite that infects a wide range of hosts, including humans and companion animals, raising concerns of zoonotic transmission. However, there is limited epidemiological information on the prevalence and genotypes of E. bieneusi in sheltered dogs and cats in Sichuan province, southwestern China. A total of 880 fecal samples were collected from shelters in different cities of Sichuan province, including 724 samples from dogs, and 156 samples from cats. Enterocytozoon bieneusi was determined by sequence analysis of the ribosomal internal transcribed spacer (ITS). Overall, the prevalence of E. bieneusi was 18% (158/880), and the parasite was detected in 18.8% (136/724) and 14.1% (22/156) of the dogs and cats examined, respectively. Sequence analysis revealed the presence of five genotypes in dogs, including three known genotypes CD9 (n = 92), PtEb IX (n = 41), and Type IV (n = 1), and two novel genotypes SCD-1 (n = 1) and SCD-2 (n = 1). Similarly, four genotypes were identified in cats, including CD9 (n = 11), Type IV (n = 6), D (n = 4), and PtEb IX (n = 1). Genotypes D and Type IV have previously been identified in humans and are reported in sheltered dogs and cats in the present study, indicating that these animals could be as potential sources of human microsporidiosis infections.