Microbes play a fundamental role in the health of all levels of marine ecosystems. Observing how microbial distributions vary over space and time can allow us to monitor the consequences of environmental change on ecosystem processes. However, our ability to forecast and mitigate the impacts of these changes requires novel approaches to project baseline observations onto broad-scale future climate scenarios. We assessed the utility of machine learning approaches to predict microbial provinces of Australia’s regional seas and oceans. Boosted regression trees (BRT) are correlative models recognised for their predictive power. We generated over 3,000 models for the most abundant microbial genotypes (Actual Sequence Variants) using extensive microbial community and environmental data collected as part of the Marine Microbes and Australian Microbiome projects. The performance of community models and predictions was evaluated with 10-fold cross validation and against independent datasets. Microbial communities were reconstructed from model predictions over 234,132 spatial points in the CSIRO Altas of Regional Seas (CARS09, 0.5˚ resolution) providing the first comprehensive spatial model of microbial communities for the Southern Hemisphere. Microbial community provinces, together with their transition zones and boundaries, were delineated using k-means and hierarchical clustering. Clear latitudinal oscillations were observed in the boundaries of microbial provinces (up to 5.0˚ in latitude) providing a powerful observation of the dynamics of microbial communities in the oceans. These species distribution models provide a framework to examine the trajectory of changes in microbial communities and processes in response to changing climate.