Recent paleobotanical investigations in Vietnam provide a good opportunity to improve our understanding of the biodiversity and paleoclimatic conditions in the geological past of Southeast Asia. Palms (Arecaceae) are a diverse family of typical thermophilous plants with a relatively low tolerance for freezing. In this study, we describe well-preserved fossil palm leaves from the Oligocene Dong Ho Formation of Hoanh Bo Basin, northern Vietnam. Characters of the fossil leaves, such as a fan-shaped costapalmate lamina, an unarmed petiole, a costa slightly enlarged at the base that then tapers distally into the blade, and well-preserved amphistomatic leaves with cuticles, suggest that they represent a new fossil species, which we herein designate Sabalites colaniae A. Song, T. Su, T. V. Do et Z.K. Zhou sp. nov. Together with other paleontological and palaeoclimatic evidence, we conclude that a warm climate prevailed in northern Vietnam and nearby areas during the Oligocene.