Enterocytozoon bieneusi is a human pathogen with a broad range of animal hosts. Initially, E. bieneusi was considered an emerging opportunistic pathogen in immunocompromised, mainly HIV-infected patients, but it has been increasingly reported in apparently healthy individuals globally. As in other African countries, the molecular epidemiology of E. bieneusi in Mozambique remains completely unknown. Therefore, we undertook a study to investigate the occurrence and genetic diversity of E. bieneusi infections in children with gastrointestinal symptoms as well as in asymptomatic children in Mozambique. Individual stool specimens were collected from 1,247 children aged between 0 and 14 years-old living in urban and rural settings in Zambézia (n = 1,097) and Maputo (n = 150) provinces between 2016 and 2019. Samples were analysed for E. bieneusi by nested-PCR targeting the internal transcribed spacer (ITS) region of the rRNA gene. All positive amplicons were confirmed and genotyped. Penalised logistic regression (Firth) was used to evaluate risk associations. The overall prevalence of E. bieneusi in this children population was 0.7% (9/1,247). A 10-fold higher prevalence was found in Maputo (4.0%; 6/150) than in Zambézia (0.3%; 3/1,097). All E. bieneusi-positive samples were from children older than 1-year of age, and most (8/9) from asymptomatic children. Nucleotide sequence analysis of the ITS region revealed the presence of four genotypes, three previously reported (Peru11, n = 1; Type IV, n = 2, and S2, n = 2) and a novel genotype (named HhMzEb1, n = 4). Novel genotype HhMzEb1 was identified in both asymptomatic (75%, 3/4) and symptomatic (25%, 1/4) children from a rural area in Maputo province in southern Mozambique. Genotypes HhMzEb1, Peru11, S2, and Type IV belonged to the Group 1 that includes genotypes with low host specificity and the potential for zoonotic and cross-species transmission. Being infected by enteric protozoan parasites and no handwashing were identified as risk associations for E. bieneusi infection. This study reports the first investigation of E. bieneusi genotypes in Mozambique with the identification of three previously reported genotypes in humans as well as a novel genotype (HhMzEb1). Findings highlight the need to conduct additional research to elucidate the epidemiology of E. bieneusi in the country, especially in rural areas where poor hygiene conditions still prevail. Special attention should be paid to the identification of suitable animal and environmental reservoirs of this parasite and to the characterization of transmission pathways.