Fondé en 1680 par Manuel Lobo (haut-gradé militaire) sur ordre de la cour de Lisbonne, Colonia sera ensuite réclamé par les immigrants espagnols qui se trouvaient à Buenos Aires de l'autre coté du Río de la Plata. Du temps des portugais, la ville s'appelait Colónia do Sacramento. La ville changera de mains durant les différents traités qui furent signés entre le Portugal et l'Espagne. Vous aurez le traité de Madrid en 1750 ou bien celui de San Ildefonso en 1777 qui mettra la ville entre les mains des espagnols. Puis de nouveau reprise par les portugais et ensuite incorporé par les brésiliens en 1816 quand l'Uruguay sera occupé par le gouvernement du Royaume-Uni de Portugal, du Brésil et des Algarves. Colonia fera parti de la Province Cisplatine (littéralement « province en-deçà du Río de la Plata » d'un point de vue brésilien). Finalement, Colonia deviendra uruguayenne au moment de l'indépendance du pays en 1828.
Comme conséquence de la bataille entre les portugais et les espagnols, la ville est un mélange de style architectural colonial. Vous trouverez des maisons de pierre de style portugais avec des toits typiques de ces périodes mélangées aux maisons de briques et toits plats classique de l'architecture espagnole. Le quartier historique a encore des rues pavées construit par les Portugais au XVIIe siècle.
