Артур Филлип был первым губернатором колонии. По состоянию здоровья ему пришлось вернуться в Англию в 1792, и на протяжении следующих трех лет два временных губернатора, Джон Хантер и Филип Гидли Кинг, поочередно пытались управлять колонией с помощью отряда, набиравшегося в Англии и известного под названием Новоюжноуэльсский корпус. Преемником этих губернаторов стал Уильям Блай, имя которого стало известно в связи с мятежом на корабле «Баунти». Блай пытался навести в колонии флотскую дисциплину и вошел в конфликт с теми, кто стремился извлечь личную выгоду из существовавших в колонии затруднений. Опираясь на богатых и влиятельных колонистов, командир Новоюжноуэльсского корпуса майор Джордж Джонстон сместил и арестовал Блая. Джонстон был осужден военным судом за участие в этой «ромовой революции», и в 1809 губернатором был назначен полковник Лаклан Маккуори.

Вместе с Маккуори в Австралию прибыло возглавляемое им войсковое соединение – 73-й шотландский полк, а Новоюжноуэльсский корпус был возвращен в Англию. Маккуори считал, что многие из бывших каторжников являются лучшими гражданами по сравнению с некоторыми вольными колонистами. Он энергично взялся за программу строительства, существенно обновил облик Сиднея, улучшил состояние дорог. Все эти мероприятия требовали немалых средств. Английское правительство, обеспокоенное расходами и склонное верить, что Макуори чересчур снисходительно относится к заключенным, направило комиссара Джона Т.Бигге для проверки состояния дел в колонии. Отчеты Бигге способствовали ужесточению тюремной дисциплины и предоставлению гражданских прав вольным колонистам.

Быстрый переход к самоуправлению в Новом Южном Уэльсе нельзя было осуществить до тех пор, пока оставались нерешенные противоречия между отбывшими срок каторжниками и вольными колонистами. Первые стремились получить право на участие в управлении, тогда как вольные колонисты не желали предоставлять политические привилегии бывшим заключенным. Комитет английского парламента в 1837–1838 рекомендовал прекратить высылку каторжников. В 1840 английское правительство утвердило эту рекомендацию в отношении Нового Южного Уэльса. Благодаря этому появилась возможность сделать очередной шаг на пути к самоуправлению колонии. По закону 1842 Новому Южному Уэльсу было предоставлено право избрать законодательный совет из 36 членов. Освобожденным каторжникам предоставлялось право голоса. Но существовал имущественный ценз. Законопроекты могли быть отклонены губернатором или направлены на рассмотрение английского правительства. Оно распоряжалось и продажей земли. Продолжалось заселение других районов Австралии. Каторжные колонии были созданы на Земле Ван–Димена (ныне о.Тасмания). Колония Западная Австралия была организована в 1826 после высадки в Албани на ее южном побережье, а колония Суон-Ривер на западном побережье поблизости от современного города Перт – в 1829, хотя ее не использовали до тех пор, пока туда не стали прибывать суда с заключенными в 1850–1868. Южная Австралия была основана не как каторжная колония: там с 1836 стали наделять землей вольных переселенцев в соответствии с проектом Эдуарда Гиббона Уэйкфилда. На территории нынешней Виктории в 1830-х годах стали обосновываться неофициальные поселенцы, которые мигрировали к югу из района Сиднея и к северу с Земли Ван-Димена. Некоторые из них устроились близ нынешнего Мельбурна. Отдельные переселенцы мигрировали также к северу от Сиднея на территорию современного Квинсленда, и в 1824 каторжное поселение было основано в районе Брисбена.