Do lado esquerdo do rio Haut du Cap, Cristóvão Colombo construiu um pequeno forte com o resto do navio Santa Maria quando este foi destruído no dia de Natal em 1492; ele nomeou o forte como La Navidad (em inglês, "Natal"). Este forte foi o primeiro edifício europeu na América.
A região ao redor da cidade tinha o nome Taíno de Guarico, o nome usado pelos colonizadores espanhóis para a região e a nova cidade. Quando os franceses vieram da Ilha Tortuga para viver aqui, fundaram a cidade em 1670 e o rei francês Luís XIV nomeou o local como Cap-Français em 1711; era então a capital da colônia de Saint-Domingue até 1770, quando Porto Príncipe se tornou a nova capital.
A cidade foi destruída pelo povo espanhol em janeiro de 1691, após a Batalha de La Limonade; La Limonade é uma savana a leste de Cap-Haïtien. Mais tarde, em 1695, a cidade foi novamente destruída por soldados espanhóis e ingleses.
O Haiti, conhecido como Saint-Domingue durante a época colonial, era a colônia mais rica da França, e Cap-Français era a cidade mais rica da colônia. A cidade era então conhecida como a "Paris do Oeste".
Durante a Revolução Haitiana, houve uma batalha em 18 de novembro de 1803 em Vertières, perto de Cap-Haïtien. Nesta batalha, o exército de Jean-Jacques Dessalines derrotou um exército colonial francês liderado pelo Comte de Rochambeau, levando à independência do Haiti em 1º de janeiro de 1804.
Após a independência do Haiti, o país foi dividido em duas partes e a parte norte foi transformada num reino por Henri Christophe e o nome da cidade foi mudado para Cap-Henry. Christophe fez de Milot, uma cidade a 15 km ao sul da cidade, a capital de seu reino.
A cidade recebeu o nome de Cap-Haïtien após a morte de Christophe e quando o Haiti se tornou novamente um país.
