Sea surface temperatures (SSTs) are significantly warming along the northwest (NW) and northeast (NE) coasts of Australia - regions containing well-protected and internationally significant tropical marine ecosystems. The magnitude and spatial distribution of observed warming of annual, maximum and minimum SSTs is examined, 1950–2007. Observed warming is comparable along the NE and NW coasts although greater along the NE coast south ∼15°S, greater at higher than lower latitudes, and greater for annual minimum than annual maximum SSTs. Average climate zones have also shifted >200 km south along the NE coast and about half that distance along the NW coast. If current trends continue, annual average SSTs in northern parts could be ∼0.5°C warmer and those of more southern parts ∼2.0°C warmer within the next 100 years. These rapid changes in oceanic climate are already causing responses in Australia's tropical marine ecosystems and these responses, if present rates of warming continue, can only intensify.