Ehrlichia canis (Rickettsiales; Anaplasmataceae) is one of the most prevalent tick-borne pathogens of dogs globally. The bacterium infects monocytes and is the aetiological agent of canine monocytic ehrlichiosis. For many decades Australia was thought to be free of the pathogen, but this abruptly changed in May 2020 when E. canis was detected in several dogs from Kununurra, Western Australia. Subsequent surveillance activities found unexpectedly large scale spread of E. canis throughout much of northern Australia. To gain insight into the genetic relationships of the Australian strain and its potential origin, we undertook a genomic analysis of E. canis positive domestic dog and tick (Rhipicephalus linnaei) samples from the north of Western Australia, the far north of South Australia and the Northern Territory, covering thousands of square kilometres. We obtained complete E. canis genomes from each of the three states, plus an additional 16 partial genomes, substantially increasing publicly available E. canis genetic resources. The Australian E. canis genomes were highly conserved across large geographic distances. Outside of Australia, the genomes were most similar to E. canis YZ-1 from China, although few reference sequences were available. We analysed the variable trp36 gene to obtain greater phylogenetic signal, which demonstrated that the Australian E. canis belonged to the Taiwan genotype, comprised of samples from Taiwan, China, Thailand and Turkey. Taken together, our findings suggest that E. canis in Australia may have originated from Asia or the Middle East and spread throughout northern and central Australia following its introduction.