Stegolophodon is an age-informative genus of mammals that had a widespread distribution during the Neogene. This paper reports the discovery of Stegolophodon fossils from the Middle Miocene lower Fotan Formation at the Zhangpu locality, Fujian Province, China. This discovery represents the first evidence of Neogene proboscidean fossils in southeastern China. The newly found molar materials have low tooth crowns, very straight lophs/lophids, and an indistinct median sulcus. The mesoconelets and posterior cingulum are well-developed, while the second posterior pretrite central conule is significantly reduced. These specimens closely resemble Stegolophodon pseudolatidens in cheek tooth morphology, and can thus be attributed to the same species. This discovery fills a gap in the fossil record of large mammals in this region during the Neogene and provides valuable insights into the evolution of proboscideans and paleoenvironments.