The largest digitized dataset of land plant distributions in Australia assembled to date (750,741 georeferenced herbarium records; 6,043 species) was used to partition the Australian continent into phytogeographical regions. We used a set of six widely distributed vascular plant groups and three non-vascular plant groups which together occur in a variety of landscapes/habitats across Australia. Phytogeographical regions were identified using quantitative analyses of species turnover, the rate of change in species composition between sites, calculated as Simpson's beta. We propose six major phytogeographical regions for Australia: Northern, Northern Desert, Eremaean, Eastern Queensland, Euronotian and South-Western. Our new phytogeographical regions show a spatial agreement of 65% with respect to previously defined phytogeographical regions of Australia. We also confirm that these new regions are in general agreement with the biomes of Australia and other contemporary biogeographical classifications. To assess the meaningfulness of the proposed phytogeographical regions, we evaluated how they relate to broad scale environmental gradients. Physiographic factors such as geology do not have a strong correspondence with our proposed regions. Instead, we identified climate as the main environmental driver. The use of an unprecedentedly large dataset of multiple plant groups, coupled with an explicit quantitative analysis, makes this study novel and allows an improved historical bioregionalization scheme for Australian plants. Our analyses show that: (1) there is considerable overlap between our results and older biogeographic classifications; (2) phytogeographical regions based on species turnover can be a powerful tool to further partition the landscape into meaningful units; (3) further studies using phylogenetic turnover metrics are needed to test the taxonomic areas.