Long, well-dated records of climate change in Australia are rare because most of the continent is prone to deflation and sediments are difficult to date beyond 40 ka. Deep-sea cores, containing terrigenous material, provide an ideal alternative to terrestrial records, because of continuous sedimentation and a robust chronology derived from oxygen isotopes. In this paper, the first of a series of two, we present pollen and spores data from core Fr1/94-GC3 from the East Tasman Plateau. This core is positioned at the southern extreme of the East Australia Current and simultaneously records changes in both oceanography and environments both offshore and in southeastern Australia. In an area of slow sedimentation, this core provides a continuous record of vegetation change in southeastern Australia and the southern Tasman Sea over approximately the last half a million years. Through time, glacial periods have progressively become warmer and shorter. Alpine plant taxa become more restricted with time and rainforest taxa expand to a far more restricted degree during the present interglacial period than the previous one, representing a fundamental shift in the vegetation of Tasmania. We apply transfer functions to reconstruct past rainfall and land temperatures based on the palynoflora that are then compared against the marine proxy record.