Each spring, billions of Bogong moths escape hot conditions across southeast Australia by migrating up to 1000 km to a place they have never previously visited – a limited number of cool caves in the Australian Alps, historically used for aestivating over summer1,2. At the beginning of autumn the same individuals make a return migration to their breeding grounds to reproduce and die. Here we show that Bogong moths use the starry night sky as a compass to distinguish geographic cardinal directions and to steer migration in their inherited migratory direction, the first invertebrate known with this ability. By tethering spring and autumn migratory moths in a flight simulator3-5, we found that under naturalistic moonless night skies, and in a nulled geomagnetic field (disabling the moth’s known magnetic sense4), moths flew in their seasonally appropriate migratory directions. Visual interneurons in different regions of the moth’s brain responded specifically to rotations of the night sky and were tuned to a common sky orientation, firing maximally when the moth was headed southwards. Our results suggest that Bogong moths use stellar cues and the Earth’s magnetic field to create a robust compass system for long-distance nocturnal navigation