La primera colonización de la Polinesia y Melanesia es aún un misterio para antropólogos e historiadores (ver cuadro «Melanesios y Polinesios»). Los polinesios arribaron a Vanuatu aproximadamente en el 1400 a.C. Recorrieron y poblaron todo el océano Pacífico, desde las proximidades de la Antártida, en el sur de Nueva Zelandia/Aotearoa, hasta Hawaii, bastante al norte del Ecuador y hasta la isla de Pascua en el extremo oriental del gran Océano. Domesticaron animales y desarrollaron algunos cultivos de subsistencia, manufacturaron cerámicas y tejidos, organizaron sociedades de castas y, en algunos casos, rudimentos históricos transmitidos oralmente durante siglos.
El 29 de abril de 1605 el navegante lusitano-español Pedro Fernández de Quirós avistó las islas y creyéndolas parte del Gran Continente Austral que pensaba hallar, las bautizó Tierra del Espíritu Santo.
Un siglo y medio más tarde el francés Louis-Antoine de Bougainville circunvaló la región y demostró que eran islas y no parte de Australia. En 1774 el capitán británico James Cook trazó el primer mapa del archipiélago, que denominó Nuevas Hébridas.
En pocos años llegaron los comerciantes, que talaron las maderas aromáticas (sándalo) y las islas se convirtieron en cantera de mano de obra semiesclava, llevada a la fuerza o comprada a los jefes locales a cambio de tabaco, espejos y armas de fuego.
Durante casi todo el siglo XIX el archipiélago estuvo entre la zona de influencia de Francia –desde Nueva Caledonia– y del Reino Unido –establecido en las Salomón–, que finalmente resolvieron compartirlo. En 1887 se estableció una Comisión Naval Conjunta y en 1906 se formalizó el Condominio, que preveía el mantenimiento en común de algunos servicios (correos, radio, aduana, obras públicas), y dejaba a cada potencia libertad para desarrollar actividades paralelas. Así había en las islas dos policías, dos monedas, dos servicios independientes de salud y dos sistemas escolares, regidos por dos representantes.
Los habitantes locales (melanesios) quedaron relegados a la condición de apátridas en su propio país –tampoco eran ciudadanos– hasta que en 1974 se estableció una asamblea legislativa del territorio. La ciudadanía británica o francesa quedaba reservada a los blancos, así como la propiedad de las mejores tierras.
La independencia de la mayoría de los archipiélagos vecinos, en la década de 1970, estimuló la fundación en 1971 del Partido Nacional de Nuevas Hébridas –hoy Vanuaaku Pati (VP), Partido de Nuestra Tierra–, que organizó grupos de base en todas las islas a partir de la estructura parroquial protestante. Cuando el Partido ganó dos tercios de los votos, en 1979, los británicos accedieron a otorgar la independencia.
La independencia fue proclamada el 30 de julio de 1980. De inmediato se tomaron medidas para devolver a los melanesios las tierras en manos de extranjeros, unificar el sistema escolar y crear un ejército nacional.
La ombudsman (defensora del pueblo) Marie-Noelle Ferrieux-Patterson denunció en 1996 que el gobierno había desviado fondos de ayuda a los damnificados por los ciclones, emitido pasaportes falsos y malversado fondos de pensiones.
El ex premier Barak Sope fue sentenciado, en julio de 2002, a tres años de prisión por falsificar certificados de garantía gubernamentales, pero fue indultado tres meses después por razones de salud.
Alfred Maseng Nalo fue electo presidente en abril de 2004 pero la Corte Suprema lo destituyó en mayo, en virtud de una norma que prohibía la elección de personas con antecedentes criminales. Maseng había sido procesado por complicidad criminal y malversación. En mayo, el primer ministro Edward Natapei perdió la mayoría parlamentaria. El presidente interino, Roger Abiut, disolvió el parlamento y convocó a elecciones para julio.
Kalkot Mataskelekele fue electo presidente en agosto por 58 miembros del Colegio Electoral, entre un total de 16 candidatos. Serge Vohor fue electo primer ministro. Mataskelekele llamó al Gobierno, la Iglesia, los líderes tradicionales y a la ciudadanía en su conjunto a unirse para lograr el desarrollo del país. Tres meses después, el parlamento votó una moción de retiro de confianza a la gestión de Vohor. Vohor recibió una controvertida evaluación por sus esfuerzos para forjar relaciones diplomáticas con Taiwán. Ham Lini fue nombrado nuevo primer ministro.
La amenaza de erupción del volcán Monte Manaro –que comenzó a despedir cenizas y humo en diciembre de 2005– determinó que miles de personas debieran ser evacuadas de la isla de Aoba.
En mayo de 2006, el Parlamento se reunió en forma extraordinaria para estudiar estudiar un paquete de leyes remitido por el primer ministro. Las medidas propuestas se referían a la administración de cárceles, la creación de un banco agrícola y enmiendas al sistema judicial, entre otros temas. En junio, el gobierno anunció un nuevo acuerdo quinquenal de desarrollo estratégico con la Agencia de Desarrollo Internacional de Nueva Zelandia (NZAID, según sus siglas en inglés) focalizado en la reducción de la pobreza, especialmente en áreas rurales.
Un estallido de violencia racial en las afueras de la capital terminó, en marzo de 2007, con 3 muertos y cientos de detenidos y heridos. Los combates entre ocupantes ilegales de tierras en las afueras de la capital y citadinos –los más violentos de la historia según la autoridades– comenzaron cuando estos últimos acusaron a los ilegales de utilizar la magia negra para matar a los dueños de las tierras.