At the end of the 18th century, apart from the indigenous people, the area was populated by the Spanish and the Portuguese alike.

In 1795, the Captain of the Spanish Infantry Agustín de la Rosa founded the town of Melo, a fortress to repel attacks of the Portuguese and the Indios.

[1] The old Posta del Chuy, 15 kilometres (9.3 mi) from the town, was the historic Inn where travellers from Melo to Villa Artigas (the actual Río Branco) could rest and pay the fares for using the first public work of the Republic, the stone bridge over the stream Chuy del Tacuarí, today a Heritage Monument, built in 1855 by the French Basque brothers Etcheverry.

During the 19th and early 20th centuries, when intermittent periods of civil war occurred in Uruguay, the department was a stronghold of the Blanco party.

As of the census of 2011, Cerro Largo Department had a population of 84,698 (41,050 male and 43,648 female) and 35,841 households.