Polymyxa graminis is an obligate parasite of roots and an important vector of viruses that damage cereal crops in different parts of the world. In 2011 and 2012, P. graminis was identified infecting 11 wheat root samples from three widely dispersed locations in southwest Australia. Its presence was detected by polymerase chain reaction (PCR) and confirmed by DNA sequencing of the transcribed regions of its ribosomal RNA genes (rDNA) and observing sporosori of characteristic morphology and size in stained wheat roots. Also, when soil samples were collected from two locations where P. graminis was found and wheat bait plants grown in them, P. graminis was detected in their roots by PCR. Ribosomal DNA sequences of six southwest Australian isolates were obtained from wheat roots, and one northeast Australian isolate from barley roots. When these seven P. graminis sequences were compared with others from GenBank by phylogenetic analysis, three southwest Australian isolates were classified as P. graminis f. sp. temperata (ribotypes Ia and Ib), and three as f. sp. tepida (ribotypes IIa and IIb). P. graminis f. sp. temperata and tepida both occur in temperate growing regions of other continents and are associated with transmission of soil-borne viruses to cereal crops. The P. graminis isolate from northeast Australia was sufficiently distinct from the five existing sequence groups for it to be placed into a newly proposed grouping, ribotype VI, which also included an isolate from tropical West Africa. However, when randomly collected wheat leaf samples from 39 field crops from 27 widely dispersed locations, 21 individual wheat plant samples collected from low lying areas within 21 fields at 11 locations, and wheat bait plants growing in five soil samples from two locations were tested by reverse transcription (RT)-PCR for the presence of Soil-borne wheat mosaic virus, Soil-borne cereal mosaic virus, Wheat spindle streak mosaic virus, and furoviruses in general, no virus infection was detected. These findings suggest at least three P. graminis introductions into Australia, and the occurrence of f. sp. temperata (ribotype I) and f. sp. tepida (ribotype II) suggests that, if not already present, soil-borne cereal viruses are likely to become established should they become introduced to the continent in the future.