We present here the earliest known Asian fossil records of the Menispermaceae based on fossil fruits from Paleocene and Eocene localities in South China. A new genus and species, Paleoorbicarpum parvum sp. nov., and two new species of Stephania Loureiro, S. ornamenta sp. nov. and S. geniculata sp. nov., are recognized from Paleocene deposits of the Sanshui Basin, Guangdong, and a new occurrence of the widespread Eocene species Stephania auriformis (Hollick) Han & Manchester is recognized from the Maoming Basin, Guangdong. The Paleocene Stephania specimens described here represent the earliest fossil endocarp record of the Menispermaceae in eastern Asia. This discovery shows that the moonseed family had arrived in tropical and humid South China by at least the middle Paleocene, which provides important evidence for the origin and phytogeographic history of the family.