Until 1834 there was not any building in Havana, used only as prison. Only the small area on the west wing of the Palacio de los Capitanes Generales that looks towards the Mercaderes street, was used as the public prison that was crammed with the prisoners. Thus, the Captain General Lieutenant General Miguel Tacón ordered the construction of a prison outside of the city walls, in an area very close to the Castillo de La Punta and at the beginning of the Paseo del Prado. It is said that Tacón wanted to give a message to the ships that entered the Bay of Havana, as this prison building was the first thing that the foreign sailors would saw. Upon inauguration of the prison of Havana that was called Real Cárcel de la Habana (Royal Jail of Havana), known also as Cárcel Nueva in the public, in 1834, the public prison in the Palacio de los Capitanes Generales was closed. Its architect was the Colonel Miguel Pastor that had also many recommendations on the design of the Fuenta de la India.

The prison was completed in 4 years, starting with the construction in 1835. Initially the building had two floors. The main facade was overlooking to the Agramonte street, the other to the Paseo del Prado. Between 1863 and 1990 several extensions were added to the main building. It occupied an rectangular area (about 75 meters in front and about 130 meters in depth), had a capacity of 2.000 prisoners, separated according to the sex, class and skin color. The part, overlooking to the Zulueta street (today Avenida de Bélgica), was used as barracks with a capacity of 1.200 soldiers. It had separate rooms for the officers.

The prison, also known as the Tacón Prison, was demolished completely in 1941. With the complete destruction of the prison, Sociedad Cubana d Estudios Históricos e Internacionales launched a campaign to reorganize the area as Parque de los Mártires de la Libertad. Emilio Roig, head of the historians, wrote a letter addressing the country's highest authority, President Fulgencio Batista, to preserve what's left of the prison in memoriam to the personalities that were imprisoned here because of their struggle for an independent of Cuba. Finally, the chapel and the four cells of the dungeon are preserved, according to the cultural project of establishing the Parque de los Mártires, also known as Parque de los Enamorados (Park of the Lovers). Within the framework of the cultural project of Parque de los Mártires, a group of artists, including Rita Longa and Domingo Ravenet, painted the walls of the chapel and decorated with various frescoes. However, only a small part of the frescoes adorning the top and walls of the chapel has survived.

The most famous figure of those who have suffered in this prison, is Jose Martí who was accused of treason and bribery. He was prisoned in one of these preserved cells during the years of 1869 and 1870, when he was 17 years old. During this period, he was forced to work under gruelling circumstances in the nearby quarries of San Lazarro. In 1871, eight Medical students sentenced to death, although they had not committed any crime, prayed in this chapel shortly before their execution.