Общая история отношений России и Австралии насчитывает более 200 лет. 16 июня 1807 года в Порт Джэксон (ныне Сидней) зашёл российский шлюп «Нева» под командованием Л. А. Гагемейстера, направлявшийся в русские колонии в Северной Америке. В первой половине XIX века в Австралии побывали российские корабли, исследовавшие Антарктиду под руководством адмиралов Ф. Ф. Беллинсгаузена, М. П. Лазарева, И. Ф. Крузенштерна и М. Н. Васильева. Первым русским учёным, открывшим Россию для Австралии, был Николай Николаевич Миклухо-Маклай.
Первые консульские представительства России в Австралии появились после окончания Крымской войны и восстановления русско-английских торговых связей. Представители коммерческих кругов Великобритании обратились в Генеральное консульство России в Лондоне с предложением учредить «в интересах торговли империи» консульские представительства России в Австралии. Вопрос был решён положительно, и в марте 1857 г. коммерсанты Дж. Дамион и Э. Пауль были назначены российскими нештатными вице-консулами в Мельбурне и Сиднее соответственно.
В конце XIX века Россия расширяла сеть дипломатических представительств в разных странах, закрепляя свои политические и торговые позиции в мире. Высочайшим указом по Министерству иностранных дел Российской империи в июле 1893 года первым штатным консулом в Мельбурн был назначен А. Д. Путята. В начале XX века сеть российских консульских учреждений в Австралии расширилась и уже охватывала Сидней, Брисбен, Дарвин, Хобарт, Ньюкасл, Перт и Порт-Пири. Первым Генеральным консулом России в Австралии был назначен М. М. Устинов в 1903 году.
После Октябрьской революции 1917 года в России официальные связи были разорваны, затем восстановлены в период Второй мировой войны. Но вплоть до 1990-х годов отношения развивались непросто.
В постсоветский период российско-австралийские отношения развиваются достаточно динамично. Расширяются политические контакты, в том числе на самом высоком уровне.
10 октября 2013 года отмечалось 70-летие установления дипломатических отношений между Россией и Австралией.
