Like other avian circovirus species, Pigeon circovirus (PiCV) is known to be genetically diverse with a relatively small circular single-stranded DNA genome of 2 kb that encodes for a capsid protein (Cap) and a replication initiator protein (Rep). Recent paleoviral evidence hints towards a probable Gondwanan origin of avian circoviruses, paralleling the evolution and dispersal of their hosts. Limited availability of PiCV genome sequence data in Australia has hindered phylogeographic studies in this species, so we screened clinically normal rock doves (Columba livia) in regional New South Wales, and demonstrated a high prevalence (76%) of PiCV infection by PCR. We also recovered 12 complete novel PiCV genomes and phylogenetic analyses revealed that PiCV circulating in Australian feral pigeons formed two strongly supported monophyletic clades. One clade resided with PiCV genomes from Poland, Australia, United Kingdom, Belgium, China, and Japan, and another basal clade was more closely related to PiCV genomes from Poland. A novel more distantly-related PiCV rep gene formed a solitary clade with weak posterior support. So we further analysed all selected partial rep gene sequences to demonstrate a likely naturally occurring spillover infection from a passerine circovirus candidate. The findings suggest that there is a high degree of genetic variation within PiCV in Columbiformes with potential greater admixture between avian circoviruses within Australia than previously known.