Extant ice-crawlers (Notoptera: Grylloblattidae) are wingless, ground-dwelling, relict, polyneopteran insects that live in Holarctic cold environments. Their closest living relatives are the similarly apterous bush-crawlers (Notoptera: Mantophasmatodea) from southern Africa, forming together a disjunct bipolar distribution. Meanwhile, numerous winged fossil insects have been assigned to Grylloblattodea, though the lack of defining synapomorphies has complicated efforts to clarify the evolutionary relationships between these fossils and modern wingless ice-crawlers. Here, we report a well preserved winged ice-crawler, Zygogrylloblatta longipalpa gen. et sp. nov., from the Albian/Cenomanian of northern Myanmar (ca 99 Ma). Zygogrylloblatta has the typical forewing venation of Mesozoic 'stem-Grylloblattodea', but also exhibits a unique unambiguous synapomorphy of extant Grylloblattidae in male genitalia (coxae IX with apical styli), making it the only fossil accurately related to crown-group Grylloblattidae. In contrast to ground-dwelling habits of extant ice-crawlers, Zygogrylloblatta has well developed wings, arolia and true foot pads, supporting a specialized arboreal lifestyle during the mid-Cretaceous. We demonstrate that Grylloblattidae diverged from some winged, arboreal ancestors prior to the mid-Cretaceous, bridging the gap between ancient stem-group and extant Grylloblattidae. Our results reveal previously unknown ecological and morphological diversity in early ice-crawlers and highlight the significance of transitional fossils in tracing the origin of this enigmatic insect lineage.