BACKGROUND: Cats have been transported as human commensals worldwide giving rise to many feral populations. In Australia, feral cats have caused decline and extinction of native mammals, but their time of introduction and origin is unclear. Here, we investigate hypotheses of cat arrival pre- or post-European settlement, and the potential for admixture between cats of different invasion events. We analyse the genetic structure and diversity of feral cats from six locations on mainland Australia, seven Australian islands and samples from Southeast Asia and Europe using microsatellite and mitochondrial DNA data. RESULTS: Our results based on phylogeographic model selection are consistent with a European origin of cats in Australia. We find genetic distinctiveness of Australian mainland samples compared with Dirk Hartog Island, Flinders Island, Tasman Island and Cocos (Keeling) Island samples, and genetic similarities between some of the island populations. Historical records suggest that introduction of cats to these islands occurred at the time of European exploration and/or in connection with the pearling, whaling and sealing trades early in the 19th century. On-going influx of domestic cats into the feral cat population is apparently causing the Australian mainland populations to be genetically differentiated from those island populations, which likely are remnants of the historically introduced cat genotypes. CONCLUSION: A mainly European origin of feral cats in Australia, with possible secondary introductions from Asia following the initial establishment of cats in Australia is reasonable. The islands surrounding Australia may represent founding populations and are of particular interest. The results of the study provide an important timeframe for the impact of feral cats on native species in Australia.