Территория современного Уоллонгонга изначально была заселена аборигенами народа Дхаравал (Dharawal). Считается, что название города происходит от слова woolyungah, которое на языке коренных жителей означает «пять островов». Первые европейцы, исследователи Джордж Басс и Мэтью Флиндерс, посетили этот регион в 1796 году. Уже в 1815 году здесь появились первые европейские поселенцы, после того как коренные жители провели их вместе со скотом по склонам эскарпа.
Дальнейшее развитие Уоллонгонга было неразрывно связано с его богатыми природными ресурсами. Ключевую роль в становлении города сыграла добыча угля, первые упоминания о месторождениях которого датируются 1797 годом. К концу XIX века Уоллонгонг стал вторым по величине производителем угля в австралийских колониях, что привлекло в регион тяжелую промышленность. В 1875 году были построены первые коксовые печи, а запуск сталелитейного завода в соседнем Порт-Кембла в 1928 году окончательно закрепил за Уоллонгонгом статус крупного промышленного центра. Для вывоза продукции в 1861 году построили конную трамвайную линию, которую в 1880 году сменили паровозы. Завершение строительства железнодорожной линии до Сиднея в 1887 году еще больше укрепило экономические связи и способствовало росту города.
В середине XIX века Уоллонгонг начал приобретать черты полноценного города. К 1856 году его население составляло 864 человека. В этот период были построены важные общественные здания, включая здание суда (1858), первую ратушу (1886) и больницу. Экономика, изначально ориентированная на сельское хозяйство и лесозаготовки, быстро переключилась на добычу угля и производство кокса. Появление газового освещения в 1883 году и развитие транспортной инфраструктуры свидетельствовали о превращении Уоллонгонга в значимый региональный центр с промышленной специализацией.