To investigate the extent of suspected hybridization between the brolga Antigone rubicunda and the Australian sarus crane Antigone antigone gillae, first noted in the 1970s, we analysed the genetic diversity of 389 feathers collected from breeding and flocking areas in north Queensland, Australia. We compared these with 15 samples from birds of known identity, or that were phenotypically typical. Bayesian clustering based on 10 microsatellite loci identified nine admixed birds, confirming that Australian cranes hybridize in the wild. Four of these were backcrosses, also confirming that wild Australian crane hybrids are fertile. Genetic analyses identified 10 times more hybrids than our accompanying visual field observations. Our analyses also provide the first definitive evidence that both brolgas and sarus cranes migrate between the Gulf Plains, the principal breeding area for sarus cranes, and major non-breeding locations on the Atherton Tablelands. We suggest that genetic analysis of shed feathers could potentially offer a cost-effective means to provide ongoing monitoring of this migration. The first observations of hybrids coincided with significantly increased opportunities for interaction between the two species when foraging on agricultural crops, which have developed significantly in the Atherton Tablelands flocking area since the 1960s. As the sarus crane is declining in much of its Asian range, challenges to the genetic integrity of the Australian sarus crane populations have international conservation significance.