The potential predictability of Australian seasonal mean rainfall at 800 stations is estimated using an analysis of variance method for the period 1957-2015 and for all twelve three-month seasons. The method estimates the contribution of the slow, potentially predictable, signal of the rainfall to the total inter-annual variance, after removing the climate noise due to intra-seasonal and weather variability. The results show that there are stations, in all seasons, where the potential predictability is relatively high, and can be greater than half of the total inter-annual variance. Largest potential predictability, coherent over eastern Australia, occurs during the transition to spring, and in spring seasons. Large and coherent potential predictability also occurs during the autumn seasons over Queensland and south-eastern Australia. For summer and the northern wet seasons, the potential predictability is larger over the northeast coastal stations, in the southeast, central east and central west of the continent. During winter, relatively large and coherent potential predictability occurs over the southeast, the central east, and in an implied northwest-southeast band across the continent. Patterns of seasonal forecast skill from the coupled Predictive Ocean Atmosphere Model for Australia are shown to be highly consistent with our estimates of the potential predictability. Factors that may influence the potential predictability are briefly discussed in the light of previous studies that have considered the relationships between the slow, potentially predictable, components of rainfall and the atmospheric and oceanic circulations. Prominent among these are the El Niño-Southern Oscillation, the Southern Annular mode and the meridional Indian Ocean Dipole.