Fertile and vegetative remains of Larix altoborealis sp. nov. have been recovered from sediments of the Eocene Buchanan Lake Formation of Axel Heiberg Island, Canadian High Arctic. Palynological and megafossil diversity and abundance data indicate that Larix was a subordinate member within a regionally diverse, mixed forest of broad-leaved and needle-leaved deciduous and needle-leaved evergreen taxa. Vegetative remains include leafy-leading shoots as well as branches with attached brachioblasts and needle fascicles. Cuticular analyses reveal that epidermal cells have distinctive undulatory anticlinal wall patterns bearing small projections. Seed cones are 14–30 mm long, 10–15 mm wide and are elliptical to ovoid, with 35 to 70 scales per cone. Ovuliferous scales are rounded to emarginate, each cone scale bearing two adaxial, winged seeds. Subtending each cone scale is a bract possessing a distinct apical tooth which does not exceed the length of the cone scale. The cuticular patterns of L. altoborealis needles are at present unique among Larix, but cone morphology indicates a relationship to the short-bracted taxa that are currently widely distributed in the boreal forests of North America and Eurasia, including L. laricina, L. sibirica, L. gmelini. Examination of bracts from L. altoborealis sp. nov. and all extant Larix indicates that bract morphology is distinctive for each species and is useful in identification. A phylogenetic scheme is developed for Larix based upon the seed-cone morphology, including features of the bract, and distribution patterns of extant and extinct species of Larix. Larix altoborealis sp. nov. is the first unequivocal report of pre-Oligocene Larix and provides insight into the early evolution and distribution of the genus.