Cette section ne cite pas suffisamment ses sources (décembre 2023). 

Pour l'améliorer, ajoutez des références de qualité et vérifiables (comment faire ?) ou le modèle {{Référence nécessaire}} sur les passages nécessitant une source.

Le 27 octobre 1492, Christophe Colomb débarqua à Cuba dans un golfe qu'il appela Porto Santo. De la description qu'il donne de l'endroit, on estime généralement qu'il s'agit de Baracoa, bien que certains auteurs optent plutôt pour Gibara ; seulement Colomb ajoute qu'il y a alentour une montagne, qui est sans aucun doute El Yunque : « ... le plus bel endroit du monde... J'entends les oiseaux chanter qu'ils ne quitteront jamais ce lieu... ». Selon la légende, Colomb aurait planté un crucifix, la Cruz de la Parra, dans les sables de l'actuel port de Baracoa. La ville espagnole se dresserait donc à l'emplacement de la colonie fondée par Christophe Colomb lors de son premier voyage. Les indigènes de l'île étaient les indiens Taïnos. On pense que le nom de la colonie provient de la langue arawak et signifie « au bord de la mer ». Ces indigènes, qui furent massacrés par les colons espagnols sur toute l'île de Cuba, ont été épargnés à Baracoa, où on trouve des descendants de l'ethnie originelle. Un héros local des amérindiens est Hatuey, qui s'enfuit de la colonie pour s'établir dans l'île d'Hispaniola, où il leva une armée Taïno pour expulser les Européens de Cuba. Selon les chroniques, Hatuey aurait été trahi par l'un des siens et condamné au bûcher. Juste avant de mourir, pressé par un prêtre de se convertir afin de faire son salut, Hatuey demanda si les Espagnols morts allaient au paradis ; devant la réponse affirmative du prêtre, il aurait déclaré ne pas vouloir s'y rendre.

Vers le 15 août 1511 (date officielle), Diego Velázquez de Cuéllar fut nommé premier gouverneur de Cuba. Il établit un comptoir dans la baie qu'il baptisa Nuestra Señora de la Asunción de Baracoa, faisant de Baracoa la première capitale de Cuba. En 1518 le comptoir reçut le droit de cité et le premier évêque de Cuba y institua le diocèse. L'endroit a conservé nombre de vestiges de l'occupation espagnole, comme les fortifications d'El Castillo, de Matachín et de La Punta, ou encore le vieux cimetière.

Au XVIe et au XVIIe siècle, l'isolement du port en fit la plaque tournante de la contrebande avec les colonies françaises et anglaises. Puis au début du XIXe siècle, la colonie fut ralliée par plusieurs planteurs français fuyant la révolution haïtienne : ils amenèrent avec eux la culture du café et du cacao.

À partir du milieu du XIXe siècle, plusieurs indépendantistes débarquèrent d'abord à cet endroit très retiré pour entreprendre la reconquête de l'île, tels Antonio Maceo et José Martí qui jouèrent un rôle important dans l'indépendance de Cuba en 1902.

Jusqu'à la révolution cubaine, le seul accès possible était par voie de mer ; puis dans les années 1960 une route de col, La Farola, longue de 120 km et reliant Guantánamo à la baie, fut excavée dans la montagne : c'est l'un des épisodes de la révolution. La construction de cette route avait d'ailleurs déjà été programmée par le gouvernement Batista. Le col s'élève à 600 m et la route d'accès comporte onze ponts.