L'explorateur britannique John Byron a été le premier Européen à voir l'atoll d'Atafu en 1765. L'officier de marine britannique Edward Edwards a vu l'atoll de Nukunonu en 1791 et des navires ont parfois continué à passer par Atafu et Nukunonu. En 1835, un baleinier américain est devenu le premier navire non insulaire du Pacifique à passer par Fakaofo.  En 1841, l'expédition Wilkes visita l'archipel et cartographia ses îles. Au milieu du XIX^e siècle, des baleiniers européens et américains commencèrent à visiter régulièrement Tokelau. Ils cherchaient à se réapprovisionner en eau douce et en vivres, mais ces interactions restèrent limitées. Les contacts occasionnels avec des baleiniers introduisirent toutefois de nouvelles marchandises et idées à Tokelau.

En 1845, des missionnaires catholiques (principalement français) et protestants (notamment ceux de la London Missionary Society) ont converti la population des îles sur lesquelles ils avaient débarqué. À ce jour, Nukunonu est majoritairement catholique tandis qu'Atafu est majoritairement protestant. Des missionnaires catholiques et protestants ont tous deux travaillé à Fakaofo, et la population y est plus mixte.

En 1863, la habitants de Tokelau ont connu le même drame que ceux de Tuvalu à la même époque. Ils furent victimes du blackbirding, un commerce d'esclaves organisé par des recruteurs de main-d'oeuvre venus du Pérou et d'autres régions pour travailler dans les plantations en Amérique du Sud. Beaucoup de Tokelauans furent enlevés et ne revinrent jamais. Presque tous les hommes furent kidnappés et la gouvernance locale passa à un système basé sur un conseil des anciens, qui existe toujours aujourd'hui.  Les atolls ont ensuite été repeuplés lorsque de nouveaux colons polynésiens et des migrants américains et européens se sont mariés avec des femmes Tokalauennes locales. 

En 1877, Tokelau (alors connu sous le nom d'îles Union) fut annexé par la Grande-Bretagne et placé sous la juridiction du haut-commissaire britannique des îles occidentales du Pacifique, basé aux Fidji. Il fut inclus dans le protectorat (plus tard une colonie) des îles Gilbert et Ellice en 1908. En 1925, le Tokelau a été confié par la SDN  à l'autorité de la Nouvelle-Zélande, qui l'a annexé en 1948.  

Tokelau est l'un des endroits les plus isolés de la planète, avec des infrastructures limitées. Jusqu'aux années 1970, l'accès à Tokelau depuis la Nouvelle-Zélande ou les autres îles du Pacifique était difficile et peu fréquent, ce qui a contribué à maintenir un mode de vie traditionnel malgré l'administration coloniale. Tokelau n'avait pratiquement pas de ressources naturelles exploitables, ce qui en faisait un territoire économiquement marginal. L'économie locale reposait principalement sur la pêche et l'agriculture de subsistance, ainsi que sur les envois de fonds de la diaspora tokelauane en Nouvelle-Zélande. Malgré l'influence néo-zélandaise et le rôle croissant du christianisme, les Tokelauans ont conservé une grande partie de leurs pratiques et coutumes traditionnelles. Les populations locales restaient fortement soudées autour de la famille et de la gestion collective des ressources naturelles des atolls.

Dans les années 1960 et 1970, Tokelau commença à obtenir une autonomie limitée au sein de l'administration néo-zélandaise, tout en maintenant ses structures traditionnelles. Le pouvoir local est en grande partie entre les mains des conseils villageois, connus sous le nom de fono. Les fono avaient une grande autonomie pour gérer les affaires locales, notamment les questions de terre, de pêche et de culture. En 1962, la Nouvelle-Zélande introduisit une nouvelle constitution pour Tokelau, renforçant l'autonomie locale en permettant aux conseils locaux de jouer un rôle plus important dans la gestion des affaires internes. En raison de l'isolement et du manque de perspectives économiques, un grand nombre de Tokelauans commencèrent à émigrer en Nouvelle-Zélande dans les années 1960 et 1970. Cette émigration massive a créé une diaspora tokelauane importante en Nouvelle-Zélande ( aujourd'hui 80% des Tokalauens vivent en Nouvelle-Zélande), avec des liens étroits entre les deux pays. Par le traité de Tokehega, signé en 1979, les revendications que les Etats-Unis maintenaient sur ces îles depuis 1856 ont été abandonnées, tandis que le Tokelau a renoncé à ses revendications sur l'île de Swains, qui fait partie des Samoa américaines.

Bien que Tokelau ait un statut de territoire dépendant de la Nouvelle-Zélande, il a obtenu une plus grande autonomie dans la gestion de ses affaires internes au cours des années 1980. Des délégations de Tokelau ont régulièrement rencontré des représentants du gouvernement néo-zélandais pour discuter des questions relatives à l'administration et au développement du territoire. Dans les années 1990, des discussions ont commencé sur le statut politique de Tokelau, notamment sur la possibilité d'obtenir une plus grande autonomie, voire l'indépendance en libre association avec la Nouvelle-Zélande, similaire à des modèles utilisés par d'autres îles du Pacifique comme les îles Cook ou Niue. 

En 1992, la Nouvelle-Zélande a commencé à travailler avec les dirigeants de Tokelau pour envisager la transition de Tokelau vers un modèle d'autogestion plus important. Cette période a vu la rédaction de nouvelles lois et règlements visant à accorder plus de pouvoirs aux autorités locales, tout en maintenant une relation spéciale avec la Nouvelle-Zélande. En 1996, Tokelau a obtenu une nouvelle constitution, renforçant encore davantage l'autonomie locale. Ce document définissait les compétences du General Fono, l'assemblée nationale de Tokelau, qui devint l'organe décisionnel principal pour les questions internes. Cette constitution a permis à Tokelau de prendre en charge de nombreux aspects de sa propre administration, tout en étant soutenu par la Nouvelle-Zélande pour les affaires internationales et de défense.

Les efforts pour réviser le statut politique de Tokelau ont culminé avec l'organisation de deux référendums visant à permettre à Tokelau de devenir un territoire en libre association avec la Nouvelle-Zélande, tout en conservant certains liens avec elle pour les affaires étrangères et la défense. En février 2006, un référendum a été organisé pour permettre aux habitants de Tokelau de décider s'ils voulaient adopter un statut de libre association avec la Nouvelle-Zélande, similaire à celui des îles Cook et de Niue. Cependant, la proposition n'a pas atteint la majorité des deux tiers requise pour être adoptée. Environ 60 % des votants se sont prononcés en faveur de cette autonomie, mais cela n'a pas été suffisant pour modifier le statut politique de Tokelau. Un deuxième référendum a eu lieu en octobre 2007, mais là encore, le seuil des deux tiers n'a pas été atteint. Le résultat a montré que, bien que de nombreux Tokelauans soient favorables à une plus grande autonomie, une partie significative de la population préférait maintenir le statut actuel, craignant que l'indépendance puisse entraîner des difficultés économiques ou une perte de soutien de la Nouvelle-Zélande.

Bien qu'un site pour une piste d'atterrissage sur Nukunonu ait été choisi en 2019, Tokelau n'a pas encore d'aéroport et n'est accessible que par une excursion d'une journée en bateau depuis les Samoa. En raison de cette dépendance aux Samoa pour le transport, Tokelau a suivi l'exemple des Samoa en 2011, et a déplacé le ligne de date internationale à l'est, sautant le 30 décembre et devenant une heure d'avance sur la Nouvelle-Zélande au lieu de 23 heures de retard.