Two thin-toed tridactyl tracks in a fluvial sandstone bed of the Eumeralla Formation (Albian) at Dinosaur Cove (Victoria, Australia) were likely made by avian trackmakers, making these the oldest known fossil bird tracks in Australia and the only Early Cretaceous ones from Gondwana. These tracks, which co-occur on the same surface with a slightly larger nonavian theropod track, are distinguishable by their anisodactyl form, hallux impressions and wide digit II–IV divarication angles. A lengthy hallux impression and other deformational structures associated with one track indicate foot movement consistent with an abrupt stop, suggesting its tracemaker landed after either flight or a hop. The single nonavian theropod track is similar to other tracks described from the Eumeralla Formation at another locality. The avian footprints are larger than most Early Cretaceous avian tracks recorded worldwide, indicating sizeable enantiornithine or ornithurine species in formerly polar environments of Australia. The avian tracks further supplement scant body fossil evidence of Early Cretaceous birds in southern Australia, which includes a furcula from the Wonthaggi Formation. Because of this discovery, Dinosaur Cove, previously known for its vertebrate body fossils, is added to a growing list of Early Cretaceous vertebrate tracksites in southern Australia.