Die früheste Bezeichnung für die Gegend um das heutige Wellington ist "Te Upoko o Te Ika a Maui" (englisch: the Head of Maui's fish) oder "Der Kopf von Mauis Fisch". Der Begriff ist auf die fischähnliche Form der neuseeländischen Nordinsel zurückzuführen. Dieses Gebiet war von jeher etwas Besonderes, da der "Kopf eines Fisches" nach den Bräuchen der Maori mehr wert ist als der Rest. Neuzeitliche archäologische Funde und Untersuchungen an gefundenen Knochen der von Einwanderern eingeführten Pazifischen Ratte (polynesischer Name: Kiore) mit Hilfe der Radiokarbonmethode belegen die Ankunft der Polynesier in Neuseeland derzeit um das Jahr 1280 n. Chr. Die Region um Wellington gilt neben dem Far North District als das erste Siedlungsgebiet des Landes. Abgesehen von diesen Entstehungsmythen gilt der polynesische Entdecker Kupe nach Legenden der Maori als erster Mensch, der das Gebiet um das heutige Wellington im 10. Jahrhundert n. Chr. betrat. Nachdem er ein paar Inseln einen Namen gegeben hatte, kehrte er, ohne das Gebiet zu "kolonisieren", wieder in seine Heimat, die polynesischen Inselgruppen, zurück. Einige Jahre später schickte ein großer Maori-Anführer namens Whatonga seine beiden Söhne Tara und Tautoki von der Mahia Peninsula an der Hawke Bay aus Richtung Süden. Nachdem die beiden den heutigen Wellington Harbour erreicht hatten, errichteten sie eine erste Siedlung auf der Miramar Peninsula (spanisch: Seeblick). Ihre Nachkommen begründeten zahlreiche aufstrebende Stämme (z. B. Ngati Tara, Ngati Apa oder Ngati Ira). Der Name Tar ist in zahlreichen geographischen Benennungen verewigt, so wurde der Wellington Harbour seit dieser Zeit als "Te Whanganui a Tara" (englisch: the great Harbour of Tara, der "große Hafen des Tara") bezeichnet, was heutzutage auch die offizielle Maori-Bezeichnung der Stadt ist. Die Bezeichnung Tararua Range zeugt ebenfalls von dieser Zeit. Nachdem 1819 Waikato-Stämme die Stämme Ngati Toa und Te Ati Awa vertrieben hatten, wanderten diese in Richtung Wellington weiter. Infolgedessen kam es zu kriegerischen Auseinandersetzungen mit den dort heimischen Stämmen.

Zur Zeit der ersten europäischen Entdecker des Gebiets durch Abel Tasman im Jahr 1642 und durch James Cook im Jahr 1770 waren die Ufergegenden am Wellington Harbour übersät mit kleinen Maori-Siedlungen, in Maori Pa genannt. Obwohl beide Seefahrer an Land anlegen und das Gebiet erforschen wollten, scheiterten sie bei ihren ersten Versuchen wegen der äußerst starken Strömung in der Cook Strait und deren schwierigen Windverhältnissen. Knapp 70 Jahre später begann die erste geplante Besiedlung durch Europäer, als William Wakefield im Auftrag der 1838 gegründeten New Zealand Company in Neuseeland große Landflächen von den Maori erwarb. Als Wakefield im August 1839 mit seinem Schiff, der Tory, im "großen Hafen des Tara" ankam, spielte der ehemals dominierende Maori-Stamm Ngati Tara keine große Rolle mehr, da er vom aufstrebenden Stamm der Te Ati Awa verdrängt worden war. Schon im folgenden Jahr, 1840, erreichten die ersten Siedler unter der Führung von Wakefield Port Nicholson und benannten die zukünftige Siedlung zu Ehren von Arthur Wellesley, 1. Duke of Wellington, einem Unterstützer der New Zealand Company, Wellington. Sie errichteten ihre erste Siedlung in Petone im Mündungsgebiet des Hutt River. Wegen häufig auftretender Überschwemmungen sahen sie sich aber gezwungen, die Ortschaft weiter nach Südwesten, nach Lambton Harbour in den heutigen Stadtteil Thorndon zu verlegen. 1846 zählte Wellington bereits knapp 4.000 Einwohner. Einige Jahre später wurde klar, dass die eingeengte Lage der Stadt kein weiteres Wachstum mehr zuließ. Daher wurde der Beschluss gefasst, große Flächen des angrenzenden Naturhafens trockenzulegen. Noch bevor man mit den Arbeiten beginnen konnte, erschütterte ein Erdbeben die Region. Am 23. Januar 1855 veränderte das Wairarapa-Erdbeben die Landschaft in und um Wellington. Mit einer Stärke von 8,2 MW wurde der Boden um bis zu 6,4 m angehoben, im Hafenbecken (Wellington Harbour) noch zwischen 0,3 und 2 m. Der Landgewinn wurde für das Stadtzentrum und später für den Bau des Flughafens genutzt. Durch die Verwerfungen verschob sich auch das Meeresufer, wodurch sich der Lambton Quay heute über 250 Meter vom Hafenbecken entfernt befindet.

Trotz aller Widrigkeiten wie Erdbeben, Großfeuer und den regelmäßig in Sturmstärke wehenden Winden entwickelte sich die dürftige Siedlung mit einigen Dutzend Bewohnern zu einem florierenden Zentrum für Im- und Export mit einem bedeutenden Hafen. 1865 wurde Wellington offiziell Neuseelands Hauptstadt; deren Verlegung aus dem schon damals viel größeren Auckland in die zentral gelegene, aufstrebende Metropole am Port Nicholson wurde als notwendig erachtet, um die wegen des Goldrausches in Otago in Otago aufkeimenden Sezessionsbestrebungen auf der Südinsel zu unterbinden. Die erste Sitzung des Parlaments fand am 7. Juli 1862 in Wellington statt, allerdings wurde Wellington erst im November 1863 nach einem Antrag von Alfred Domett zur Hauptstadt erklärt, in dem es hieß: "Es ist notwendig geworden, den Regierungssitz "in einen passenden Ort in der Cook Straße zu verlagern". 1886 erhielt die Siedlung Stadtrechte. Mit der Weiterentwicklung der Schifffahrtindustrie wurden zahlreiche große Lagerhallen und Produktionsstätten im Hafengebiet nicht mehr benötigt. Viele Hallen wurden modernisiert und dienten fortan anderen Zwecken (Museum, Einkaufskomplex, Wohnungen oder Büros); andere wurden abgerissen und in Parks umgewandelt. Im April 1968 sank bei einem Sturm vor der Küste Wellingtons die Autofähre Wahine. Das Schiffsunglück, das 53 Menschenleben kostete, wird als die schlimmste Schiffskatastrophe in der Geschichte des Landes angesehen, auch wenn bei früheren Schiffsunglücken höhere Opferzahlen zu beklagen waren. Über die Jahre hinweg verwandelte sich Wellington von einer kleinen, verschlafenen Landeshauptstadt zu einer wichtigen Kultur- und Lifestylemetropole des Landes. Dazu trägt neben den zahlreichen Museen und Theatern eine lebendige Musik- und Filmszene bei.