Inheemse geschiedenis
De eerste mensen die in de omgeving van Williamstown woonden, waren de Yaluki-willam clan van het Kulin volk, een inheems Australisch volk. Zij leefden en jaagden langs de kust van Werribee tot Williamstown. De Yalukit-willam maakten deel uit van de Bunurong, een taalgroep van zes clans langs de kust van de Werribee River, tot het Mornington Peninsula, Western Port Bay en Wilsons Promontory. Zij aten schelpdieren, vogels, vis, paling, eieren, slangen, kangoeroes en buidelratten die overal op hun land voorkwamen. Zij noemden Williamstown, "koort-boork-boork", ("She-oak, She-oak, veel") wat betekent "veel she-oaks", een inheemse boom. Het hoofd van de Yalikut-willam stam ten tijde van de komst van de eerste blanke kolonisten was Benbow. Hij werd een gids voor John Batman, de eerste Europeaan die zich in Melbourne vestigde.
Het aantal inheemse mensen daalde snel na 1835 als gevolg van ziekten zoals tyfus. Door racisme en het verlies van jachtgebieden was het voor hen onmogelijk hun traditionele levensstijl te handhaven.
Verkenning en vestiging
De eerste Europeaan die in Williamstown aankwam was waarnemend luitenant Robbins, die in 1803 Point Gellibrand verkende. De monding van de Yarra-rivier werd later in mei en juni 1835 verkend door John Batman. Hij dacht dat het gebied dat nu Melbourne heet, een goede vestigingsplaats zou zijn. De plaats van Williamstown noemde hij Port Harwood, naar de kapitein van een van zijn schepen.
In november 1835 zeilde kapitein Robson Coltish van de bark Norval uit Launceston, met een lading van 500 schapen en 50 Hereford runderen. Kapitein Coltish koos het gebied dat nu bekend staat als Port Gellibrand, als een goede plek om zijn lading te lossen. Binnen enkele weken begonnen veel schepen de Bass Strait over te steken. Vanwege de beschutte haven besloten veel mensen zich in de directe omgeving te vestigen.
Gouverneur Richard Bourke en kapitein William Lonsdale bezochten de nieuwe nederzetting bij Port Phillip Bay in 1837. Beiden dachten dat de belangrijkste nederzetting aan de monding van de rivier zou komen. Ze doopten het om tot William's Town, naar de koning, Willem IV. Het was de eerste haven van Melbourne en de haven voor het district Port Phillip tot het einde van de 19e eeuw.
William's Town werd genoemd naar de koning en Melbourne werd genoemd naar de Britse eerste minister Lord Melbourne. Dit deed de mensen geloven dat William's Town de hoofdstad van de nieuwe kolonie zou worden. De eerste straten van het oude William's Town werden in 1837 met dat doel aangelegd. Maar door een gebrek aan zoet water in William's Town werd het noodzakelijk het centrum van de stad te verplaatsen naar de plaats Melbourne in het binnenland.
De eerste landverkopen vonden plaats in 1837. Veroordeelden bouwden een 30 meter lange stenen aanlegsteiger in 1838. Dit is waar Gem Pier nu staat. In datzelfde jaar startte een veerdienst tussen Melbourne en Williamstown. De stoomboot 'Fire Fly' vervoerde passagiers, schapen en vee uit Tasmanië. In 1839 beschikte Williamstown over een pier en door veroordeelden gebouwde regeringswinkels. Het belangrijkste deel van de stad was gecentreerd op Nelson Place. Er werden ongeveer 100 gebouwen gebouwd, waaronder twee hotels, de Ship Inn en de Woolpack. Op Point Gellibrand werd de eerste begraafplaats van Victoria aangelegd.
De eerste vuurtoren, gemaakt van hout met een olielamp op de top, werd in 1840 gebouwd bij Point Gellibrand. In datzelfde jaar werd in Williamstown een opzichter van de waterpolitie aangesteld (en Williamstown is de huidige thuishaven van de Victoriaanse waterpolitie).
In 1841 woonden er volgens de volkstelling ongeveer 259 mensen in Williamstown. Aangenomen wordt dat het er veel meer waren. In 1841 waren er drie hotels in Williamstown en de meeste mannen werkten in de haven. Omdat het een drukke haven was, waren er talrijke logementen en een voortdurend wisselende bevolking. In de jaren 1842 en 1843 was er een economische recessie en liep het inwonertal van Williamstown terug.
In 1842 bracht de aankomst van het schip Manilus de kleine kolonie in rep en roer. Vijfenveertig van de 243 passagiers van het schip waren tijdens de reis vanaf de Schotse kusten aan gele koorts gestorven. De zieken werden naar een snel gebouwd quarantainekamp gebracht. De overledenen werden begraven op een geïmproviseerd kerkhof.
Eveneens in 1842 werd de St Mary's School (de oudste nog functionerende katholieke school in Victoria) opgericht in een kleine houten kapel met een dak van houten dakspanen. Mr. John Wilson was de eerste leraar/schoolhoofd. Volgens de vroegste gegevens waren er in juli 1844 zes jongens en acht meisjes.
In 1847 werd de Steamboat Pier gebouwd en werd er een permanent douanehuis ingericht. De waterpolitie en douane bleven hier tot de Melbourne Harbour Trust in de jaren 1890 riviergeulen aanlegde die dichter bij het Melbourne CBD lagen.
In 1849-50 werd een arduinen vuurtoren gebouwd ter vervanging van de houten vuurtoren. Hij heeft slechts tot 1860 als vuurtoren gefunctioneerd, toen er een paallicht werd gebouwd dat voor Shelly Beach werd verankerd. Daarna werd hij gebruikt als tijdbaltoren.
