Maoríes polinesios llegaron a Tokelau aproximadamente en el siglo IX, desarrollando una cultura tribal de gran afinidad con la tierra (se auto designaron guardianes de la tierra para dar el futuro).
En 1765, el explorador inglés John Byron recorrió las islas. Las escasas riquezas demoraron hasta 1877 la conversión de las islas en protectorado inglés. Fueron anexadas en 1916, incluidas como parte de la colonia de las islas Gilbert y Ellice (hoy Kiribati y Tuvalu). En 1925 se transfirió su control administrativo a Aotearoa/Nueva Zelandia. En 1946 se las llamó Tokelau y en 1958 se otorgó la soberanía a Aotearoa/Nueva Zelandia.
La política neozelandesa se ha propuesto no alterar las costumbres, las instituciones tradicionales, ni las relaciones comunitarias. Hasta 1990, un solo barco realizaba viajes regulares desde Apia (Samoa), cada dos o tres meses. No existen infraestructuras o puertos adecuados que fomenten el turismo.
En la década de 1980 la agricultura sufrió una crisis debido a fenómenos climáticos adversos. El número de emigrantes hacia Aotearoa/Nueva Zelandia y Samoa aumentó considerablemente. El gobierno de Aotearoa intentó incentivar el regreso a sus tierra, sin éxito.
En 1976 y 1981 informes de enviados de las Naciones Unidas indicaron que los habitantes de las islas no deseaban modificar la relación con Aotearoa. En diciembre de 1984, la Asamblea de la ONU resolvió mantener la decisión de que Aotearoa, como potencia administradora, informe periódicamente sobre su gestión. Sin embargo, ante el Comité Especial de la ONU en junio de 1987, Tokelau expresó su deseo de alcanzar, dentro del mismo marco, una mayor autonomía en sus asuntos políticos.
En febrero de 1990 el país fue arrasado por el ciclón Ofa, que destruyó todos los bananeros y el 80% de los cocoteros, además de hospitales, escuelas, casas y puentes. Como consecuencia, aumentó la emigración.
En 1991, se instaló el primer servicio marítimo regular entre los tres atolones.
En mayo de 1995 el parlamento aotearoano votó una extensión de poderes para la asamblea local. En 1997 llegó la telefonía satelital.
La Asistencia Oficial para el Desarrollo de Aotearoa/Nueva Zelandia (NZODA) destinó a Tokelau un presupuesto de 7,5 millones de dólares neozelandeses en 2000.
El Ministerio de las Islas del Pacífico de Aotearoa/Nueva Zelandia implementó en 2001 programas de desarrollo de políticas, para facilitar el autogobierno de Tokelau.
Entre 2002 y 2003, se sumaron al presupuesto de las islas fondos adicionales para la construcción de la infraestructura edilicia del futuro gobierno.
Aparte de Aotearoa, Australia ha mantenido acuerdos de colaboración con las islas. Durante 2002 y 2003, fondos australianos fueron volcados en educación.
Tokelau comenzó en 2004, con la asistencia del Secretariado de la Comunidad del Pacífico (SPC) y del gobierno de Samoa, un programa de desarrollo de la pesca en las aldeas, que incluyó los tres atolones Fakaofo, Nukunonu y Atafu.
El entrenamiento de cada comunidad estuvo a cargo de la SPC y de los departamentos de pesca de Samoa. Los atolones mantienen leyes para la preservación de la costa marina y las especies para futuras generaciones.
Un referéndum impulsado por la ONU, en febrero de 2006, para decidir sobre el estatus de Tokelau en relación a Nueva Zelandia arrojó 349 votos en favor del Estado Libre Asociado, contra 581 en favor de continuar como dependencia. Era necesario alcanzar una mayoría de dos tercios para aprobar la medida. Una nueva consulta se realizaría en noviembre de 2007.