Aan de linkerkant van de rivier Haut du Cap bouwde Christoffel Columbus een klein fort met de rest van het schip Santa María toen het op Eerste Kerstdag in 1492 werd verwoest; hij noemde het fort La Navidad (in het Engels, "Kerstmis"). Dit fort was het eerste Europese bouwwerk in Amerika.
De streek rond de stad had de Taíno naam Guarico, de naam die de Spaanse kolonisten gebruikten voor de streek en de nieuwe stad. Toen Fransen van het eiland Tortuga hier kwamen wonen, stichtten zij de stad in 1670 en de Franse koning Lodewijk XIV noemde de plaats in 1711 Cap-Français; het was toen de hoofdstad van de kolonie Saint-Domingue tot 1770, toen Port-au-Prince de nieuwe hoofdstad werd.
De stad werd in januari 1691 door Spanjaarden verwoest, na de Slag bij La Limonade; La Limonade is een savanne iets ten oosten van Cap-Haïtien. Later, in 1695, werd de stad opnieuw verwoest door Spaanse en Engelse soldaten.
Haïti, in de koloniale tijd bekend als Saint-Domingue, was de rijkste kolonie van Frankrijk, en Cap-Français was de rijkste stad in de kolonie. De stad stond toen bekend als het "Parijs van het westen".
Tijdens de Haïtiaanse Revolutie vond op 18 november 1803 een veldslag plaats in Vertières, bij Cap-Haïtien. In deze veldslag versloeg het leger van Jean-Jacques Dessalines een Frans koloniaal leger onder leiding van de Comte de Rochambeau, wat leidde tot de onafhankelijkheid van Haïti op 1 januari 1804.
Na de onafhankelijkheid van Haïti werd het land in twee delen verdeeld en het noordelijke deel werd door Henri Christophe een koninkrijk gemaakt en de naam van de stad werd veranderd in Cap-Henry. Christophe maakte van Milot, een stad 15 km ten zuiden van de stad, de hoofdstad van zijn koninkrijk.
De stad kreeg de naam Cap-Haïtien na de dood van Christophe en toen Haïti weer één land werd.
