Mandrills (Mandrillus sphinx) are enigmatic primates endemic to central Africa and are threatened by habitat loss and hunting. However, effective management of this species is limited by insufficient information about their numbers in the wild, since population size can impact viability and genetic diversity. Here, we used for the first time a non-invasive genetic approach to estimate the census and effective population size (Nc and Ne respectively) of a wild mandrill horde in Lopé National Park (Gabon). We amplified a total of 232 unique genotypes using a panel of 16 microsatellite loci from mandrill fecal samples collected over three years (2016–2018). Using the single sample estimator in CAPWIRE, we obtained an estimate for Nc of 989 (95% CI 947–1399) individuals which was close to that obtained from the multiple sample estimator implemented in the program MARK [992 (95% CI 708–1453)]. These estimates approximately correspond with previous visual counts obtained from the same horde. Based on a model implemented in the program NeOGen, when samples were pooled across all three sampling sessions, statistical power was sufficient for a robust Ne estimate. Using the three one-sample estimators in the NeESTIMATORV2 program and the one in COLONY, Ne was estimated at 292 (95% CI 239–370) and 135 (95% CI 108–176) individuals respectively, indicating that Ne is between 13.6 and 29.5% of Nc. This study showed that non-invasive genetics is an effective tool for providing accurate estimates of horde sizes of mandrills and other elusive primates, provided enough samples and hypervariable loci are genotyped.