A Cadeia da Relação do Porto foi criada em 27 de Julho de 1582.
Por falta de instalações próprias, começou por funcionar na Câmara Municipal, então instalada na Rua de S. Sebastião, no edifício que, por causa disso, passou também a ser conhecido por Paço Rolaçon. Poucos anos depois o Tribunal transferiu-se para o palácio dos Condes de Miranda (onde permaneceu até 1608) no desaparecido Largo do Corpo da Guarda que ficava ao cimo da rua que ainda existe com esta denominação. Os desembargadores eram obrigados a usar barba comprida e a não fazer visitas.
A Relação manteve-se em actividade, sem sede própria, durante mais de vinte anos. Com efeito foi só em 1603 que Filipe I ordenou que se construísse uma casa para receber a Relação e a Cadeia. Também esta sofria do mal do tribunal falta de instalações. Andou pela Albergaria dos Palmeiros (1461), que ficava perto da actual Rua de S. João; aparece referenciada, em 1490, num casebre entre as ruas Chã das Eiras e de Santo António do Penedo, numa artéria que ainda há pouco se chamava Travessa da Cadeia; depois instalou-se (1504) numa casa junto à Sé e mais tarde nos baixos da Casa da Câmara. A ordem de Filipe I, no entanto, só começou a ser cumprida em Julho de 1606, quando, sob a direcção do corregedor Manuel Sequeira Novais, se deu início às obras no Campo do Olival. Os trabalhos duraram três anos e foram pagos, em grande parte, com dinheiros provenientes das remissões dos degredos para África. Isto é, quem era condenado a degredo para a “costa de África” se pagasse uma determinada quantia, resgatava a pena que cumpria cá.
O edifício, considerado enorme, custou tanto dinheiro que durante o tempo da sua construção não foram feitas mais obras na cidade. No entanto, deve ter sido mal construído porque no dia 1 de Abril de 1752, em Sábado de Aleluía, ruiu completamente e a Relação regressou às instalações da Câmara Municipal.
Uma nova casa para a sede da Relação e da Cadeia começou a ser construída sobre os escombros da anterior, em 1765, por iniciativa do regedor das Justiças e governador das Armas do Porto, João de Almada Melo, segundo uma planta elaborada para o efeito pelo engenheiro e arquitecto Eugénio dos Santos Carvalho que foi um dos intervenientes na reconstrução da Lisboa pombalina. A obra que custou 200 contos, durou trinta anos, pois só ficou concluída em 1796. Albergou a sede do Tribunal da Relação e serviu de cadeia até aos nossos dias.
É um dos edifícios de referência na história do Porto. As enxovias tinham nomes de santos: Santo António, Sant’ Ana, para homens; Santa Teresa, para mulheres; e Santa Rita para menores. A prisão oficina estava sob a protecção do Senhor de Matosinhos e as prisões de castigo tinham por patrono S. Victor. Havia ainda os salões (do Carmo e de S. José) para homens e mulheres. Diferenciavam-se das celas por terem o chão de madeira mas pagava-se para ficar neles 1$500 reis.
Na sala do tribunal havia uma capela porque as Ordenações do Reino determinavam que “o governador acolherá um sacerdote, que em todos os dias pela manhã diga missa na casa da Relação no Oratório…”. Os presos ouviam a missa das grades das prisões e corredores que davam para o saguão. Mas como não havia, mesmo assim, capacidade para tanta gente, a missa era num Domingo para o detidos de determinadas celas e no outro Domingo para os das outras prisões.
A algumas das celas andam ligados nomes famosos. No número 8 dos chamados quartos de Malta (eram catorze) passou, por exemplo, o duque da Terceira (António José de Sousa Manuel e Meneses Severim de Noronha) lugar tenente da rainha D. Maria II nas províncias do Norte, detido em Outubro de 1846, juntamente com vários generais e oficiais; Camilo Castelo Branco ocupou (1860) o quarto número 12, enquanto a Ana Plácido recolhia ao pavilhão das mulheres, acusados, ambos, do crime de adultério. Na cela que Camilo ocupara daria entrada mais tarde o célebre banqueiro Roriz. E no quarto a seguir (13) esteve Urbino de Freitas, professor da faculdade de Medicina, acusado de ter assassinado por envenenamento uns sobrinhos para ficar senhor da herança que a eles caberia. O salteador José do Telhado, o caudilho miguelista Pita Bezerra e o jornalista e político João Chagas também conheceram as masmorras da velha cadeia.
Em 1961 começa a ser construído o novo estabelecimento prisional do Porto, em Custóias, com plano do arquitecto Rodrigues Lima. No entanto, a estrutura inicial foi abandonada e o edifício, que se pretendia modelar nunca acabou de ser construído. Foi rapidamente ocupado pelos reclusos da Cadeia da Relação, por razões de força maior e conforme determinação superior, em 29 de Abril de 1974. Assim o novo Estabelecimento Prisional do Porto, em Custóias, que passou a receber irregularmente reclusos preventivos, que devem aguardar julgamento próximo do local do tribunal, como acontecia na cidade do Porto -, foi alargado para aumentar a sua capacidade, substituindo a Cadeia da Relação.
Em 1974, deu-se a ocupação revolucionária do edifício da Cadeia da Relação. Várias famílias e grupos não familiares procuraram aí abrigo e durante largo tempo o edifício sofreu um desgaste inesperado, degradando-se rapidamente.