История русских в Австралии, несомненно, начинается с ярких и увлекательных описаний, составленных мореплавателями и путешественниками, посетившими этот далекий южный континент еще на заре XIX в. Многочисленные кругосветные плавания русских кораблей, важные географические открытия в районах Тихого океана и Антарктики, исследование австралийских берегов и островов и первые посещения русскими мореплавателями Порт-Джексона в Сиднейской бухте вошли в историю Австралии, Англии, России и всего мира. Есть даже несколько легенд о том, как русские участвовали в поисках неведомого материка «Терра Аустралис» и еще в 1705 г. побывали в Новой Голландии, как тогда называлась Австралия. Согласно одному из этих рассказов, Петр I уполномочил русского моряка плыть в Южные моря в 1703 г. вместе с голландцами. Хотя такое плавание было вполне вероятным (ибо совершалось несколько раз португальцами и голландцами до официального первооткрывателя Австралии Джеймса Кука), точных подтверждений этим легендам, увы, нет. Однако достоверно известно, что в XIX в. русские корабли так часто бороздили Тихий океан и так часто заходили на отдых и ремонт в Порт-Джексон, что место их обычной стоянки около Нютрал-Бэй стали называть «Русским мысом». И лишь много позднее он был переименован в Киррибилли.
Описание прибытия самого первого русского корабля в Сиднейскую бухту, а случилось это 16 июня 1807 г., появилось в «Сиднейской газете» (The Sydney Gazette) 21 июня 1807 г., после чего каждое прибытие русских кораблей отмечалось в местной прессе. Этим первым кораблем было судно «Нева» под командой капитана Леонтия Андреевича Гагемейстера.
Судя по газетным заметкам и воспоминаниям русских мореходов и австралийских губернаторов, отношения между гостями и хозяевами были исключительно дружественными. Это и неудивительно. Вступив на престол в 1801 г., Александр I тотчас же заключил Конвенцию о взаимной дружбе с Англией, а в 1804 г. был подписан военный договор России с Англией и была составлена новая коалиция против Франции. Победа России над Наполеоном в 1812 г. фактически была спасением и для Англии. Кроме того, между русским Императорским флотом и английским Королевским флотом существовала тесная связь: русские офицеры проходили практику на английских кораблях, англичане же служили по контракту в русском флоте. Так, например, знаменитый русский навигатор Михаил Петрович Лазарев, приводивший между 1813 и 1825 г. свои корабли в Австралию четыре раза, в начале своей карьеры служил в британском флоте. А среди участников первых плаваний в Австралию на русских кораблях было два английских офицера. Таким образом, неудивительно, что к началу 1820-х гг. русские мореходы получили в Австралии статус «наиболее благоприятствуемой нации».
Русские визитеры привозили интересные новости, рассказывали о своих открытиях, заключали торговые договоры и удивляли местных жителей постройкой бань на берегах Киррибилли. В свою очередь, мореплаватели с интересом наблюдали за жизнью колонии, за аборигенами, изучали необычную флору и фауну Австралии. Их записи и зарисовки являются ценным историческим свидетельством.
Так, во время приемов, балов, экскурсий и совместных работ в порту происходило знакомство австралийцев с русскими, начавшееся на очень дружелюбной ноте. Хотя, конечно, не обошлось без событий, взволновавших жизнь колонии. Например, во время первого посещения Тасмании в мае и июне 1823 г. на фрегате «Крейсер» произошел мятеж. Воспользовавшись отсутствием капитана М. П. Лазарева, взбунтовавшиеся моряки объединились со сбежавшими каторжниками и скрылись в лесу, что напугало тасманского губернатора полковника Уильяма Сорелла (1817–1824), так как Хобарт в то время был слабо защищен. Офицеру фрегата Д. И. Завалишину удалось вернуть всех матросов, кроме одного — Станислава Станкевича, оставшегося в Австралии. Однако этот матрос не стал первым русским эмигрантом, потому что самым первым эмигрантом оказался ссыльный — бывший офицер русской армии во время царствования Екатерины II.