Contact zones between subspecies or closely related species offer valuable insights into speciation processes. A typical feature of such zones is the presence of clinal variation in multiple traits. The nature of these traits and the concordance among clines are expected to influence whether and how quickly speciation will proceed. Learned signals, such as vocalizations in species having vocal learning (e.g. humans, many birds, bats and cetaceans), can exhibit rapid change and may accelerate reproductive isolation between populations. Therefore, particularly strong concordance among clines in learned signals and population genetic structure may be expected, even among continuous populations in the early stages of speciation. However, empirical evidence for this pattern is often limited because differences in vocalisations between populations are driven by habitat differences or have evolved in allopatry. We tested for this pattern in a unique system where we may be able to separate effects of habitat and evolutionary history. We studied geographic variation in the vocalizations of the crimson rosella (Platycercus elegans) parrot species complex. Parrots are well known for their life-long vocal learning and cognitive abilities. We analysed contact calls across a ca 1300 km transect encompassing populations that differed in neutral genetic markers and plumage colour. We found steep clinal changes in two acoustic variables (fundamental frequency and peak frequency position). The positions of the two clines in vocal traits were concordant with a steep cline in microsatellite-based genetic variation, but were discordant with the steep clines in mtDNA, plumage and habitat. Our study provides new evidence that vocal variation, in a species with vocal learning, can coincide with areas of restricted gene flow across geographically continuous populations. Our results suggest that traits that evolve culturally can be strongly associated with reduced gene flow between populations, and therefore may promote speciation, even in the absence of other barriers.