'Background:' Later Pleistocene human evolution in East Asia remains poorly understood owing to a scarcity of well described, reliably classified and accurately dated fossils. Southwest China has been identified from genetic research as a hotspot of human diversity, containing ancient mtDNA and Y-DNA lineages, and has yielded a number of human remains thought to derive from Pleistocene deposits. We have prepared, reconstructed, described and dated a new partial skull from a consolidated sediment block collected in 1979 from the site of Longlin Cave (Guangxi Province). We also undertook new excavations at Maludong (Yunnan Province) to clarify the stratigraphy and dating of a large sample of mostly undescribed human remains from the site. 'Methodology/Principal Findings:' We undertook a detailed comparison of cranial, including a virtual endocast for the Maludong calotte, mandibular and dental remains from these two localities. Both samples probably derive from the same population, exhibiting an unusual mixture of modern human traits, characters probably plesiomorphic for later Homo, and some unusual features. We dated charcoal with AMS radiocarbon dating and speleothem with the Uranium-series technique and the results show both samples to be from the Pleistocene-Holocene transition: ~14.3-11.5 ka. 'Conclusions/Significance:' Our analysis suggests two plausible explanations for the morphology sampled at Longlin Cave and Maludong. First, it may represent a late-surviving archaic population, perhaps paralleling the situation seen in North Africa as indicated by remains from Dar-es-Soltane and Temara, and maybe also in southern China at Zhirendong. Alternatively, East Asia may have been colonised during multiple waves during the Pleistocene, with the Longlin-Maludong morphology possibly reflecting deep population substructure in Africa prior to modern humans dispersing into Eurasia.