Se desconocen numerosos detalles de los oceanianos, que arribaron desde el sureste asiático hace unos cincuenta mil años y se establecieron en el Pacífico occidental. Entre el 7000 y el 5000 a.C. nuevas olas migratorias de la misma procedencia aportaron a esta región la agricultura, la construcción de canoas y la elaboración de cerámica. Legaron túmulos funerarios en Grande Terre y en la isla de los Pinos, además de petroglifos en la isla principal. La zona acogió nuevas migraciones desde la actual Polinesia y Samoa entre los siglos XI y XVIII. A finales del siglo XVI los españoles surcaron el Pacífico en busca de la mítica Terra Australis y, atraídos por las historias sobre el buen salvaje y los paraísos del Pacífico, ingleses y franceses les siguieron los pasos de inmediato.
El explorador británico James Cook divisó Grande Terre en 1774 y la bautizó Nueva Caledonia, al recordarle a las Highlands escocesas, denominadas Caledonia por los romanos. Catorce años más tarde, el rey Luis XVI mandó una expedición bajo el mando del conde de La Pérouse; nunca arribó debido a un ciclón frente a las costas de Vanikolo, en las islas Salomón. El almirante Bruny D_Entrecasteaux fue enviado a buscarles tres años más tarde y, junto a parte de su tripulación, desembarcó y tardó un mes en cruzar a pie el norte de Grande Terre. Los primeros occidentales que permanecieron más de tiempo fueron los balleneros británicos y estadounidenses, que habilitaron una estación de extracción de petróleo en Lifou, en las islas de la Lealtad, en 1840. Les siguieron los taladores de sándalo, cuyo establecimiento en el archipiélago generaría las primeras tensiones. En 1853, Napoleón III anexionó Grande Terre a Francia bajo el pretexto de proteger a los misioneros galos. Los franceses se instalaron y gobernaron con un régimen militar durante el resto del siglo XIX.
A medida que las misiones francesas iban adquiriendo más poder, las costumbres tradicionales se iban desintegrando y el modus vivendi de los isleños se veía amenazado. La esclavitud, que siguió hasta el siglo XX, y las nuevas enfermedades diezmaron más si cabe a la población. Los franceses consideraron el Pacífico como un lugar idóneo para ubicar a los reos, y deportaron a sus primeros convictos en mayo de 1864. La mayoría se trataba de presos políticos de la Comuna de París, pero otros eran los parias y ladronzuelos de las calles de la metrópoli. Cuando la deportación fue prohibida en 1879, Francia ya había mandado a veintiun mil prisioneros. El descubrimiento de níquel y la llegada de pobladores libres exacerbó los conflictos raciales, pues los europeos invadieron aún más tierras tribales. En 1878, una revuelta de siete meses contra el dominio francés acabó con la vida de 200 franceses y 1.200 nativos. La represión que siguió debilitó en mayor medida su cultura.
Numerosos canacos fueron reclutados en la I Guerra Mundial. Durante la segunda gran contienda, cuarenta mil soldados estadounidenses sirvieron en la base de Nueva Caledonia, que empleó a innumerables indígenas. En estas instalaciones se mantuvieron relaciones relativamente estables entre blancos y negros, y los aborígenes recibieron un sueldo real por primera vez. Finalizada la II Guerra Mundial, el estatus de la colonia fue elevado a territorio de ultramar francés.
Los canacos iniciaron la reivindicación independentista, y el líder Naisseline de Maré preparó un Estatuto de los Nativos, arguyendo que, puesto que habían luchado y fallecido en defensa de la bandera francesa, merecían los mismos derechos que los ciudadanos galos. Los indígenas obtuvieron la ciudadanía en 1946. En 1953 se fundó el primer partido político, la Union Calédonienne, y cuatro años después obtuvieron el derecho al voto. El auge del níquel en la década de 1960 condujo a un rápido crecimiento en Nouméa e incrementó tanto la agitación canaca por los derechos de la tierra como el deseo de los caldoches por obtener una mayor cuota de independencia de su lejana administración. Los primeros estudiantes formados en universidades francesas regresaron a Nueva Caledonia a finales de los años sesenta. Habían presenciado las protestas estudiantiles de mayo de 1968 en París, y la conciencia y agitación política fue en aumento.
La independencia y la devolución de las tierras constituía la clave en 1977, pero los canacos ya se habían convertido en minoría en su propio territorio. El punto de inflexión del movimiento independentista aconteció en 1984, iniciándose dos años de caos generalizado conocido como Les Évènements. Desencantados con las vacías promesas de reforma del gobierno socialista francés, varios partidos independentistas crearon el FLNKS (Front de Libération National Kanak et Socialiste), con Jean-Marie Tjibaou como su primer dirigente. El Frente boicoteó las elecciones territoriales de 1984 y la violencia sacudió el país. Cuando uno de los líderes más radicales del FLNKS fue asesinado por los paramilitares cerca de La Foa, los disturbios estallaron de forma generalizada. Francia envió tropas de inmediato y declararó el estado de emergencia.
Acontecieron nuevos boicots electorales, seguidos de asesinatos y bombas que destruyeron el centro de Nouméa; más tarde se facilitaron ciertas concesiones. Francia se enemistó con Australia y Naciones Unidas en 1986, cuando la ONU situó de nuevo a este territorio en su lista de descolonizaciones. Los franceses interpretaron este gesto como una intromisión en su política interior y expulsaron al cónsul general australiano de Nouméa, alegando que había desempeñado un papel decisivo en este proceso. Tjibaou fue asesinado en 1989 por un grupo de canacos que consideraba que el FLNKS se había vendido con el acuerdo de paz de 1988. La violencia aminoró durante la década de 1990, y las palabras que más suenan en la actualidad en la derecha y en muchos círculos independentistas son consenso e independencia negociada.
Los Acuerdos de Nouméa de principios de 1998 supusieron un golpe para la liberación nacional, pues aplazaban la independencia del territorio hasta 2013. La razón de este retraso recayó en los temores de que un referéndum pudiera suscitar nuevos brotes de violencia. Lo más probable es que Francia considere Nueva Caledonia como un bien político y económico que no desea perder.
Mientras tanto, el asunto de la independencia define la política y las relaciones étnicas. En junio de 2004, fue elegida presidenta Marie-Noelle Themerea, del partido anti-independencia Futuro Juntos, y prometió aplicar reformas sociales, económicas y fiscales.