Foi construído em 1586 por jesuítas, sendo residência dos jesuítas até o ano de 1771, quando passou a ser residência do Governo da Paraíba. Em 1773, foi incorporado a Fazenda Pública pelo Papa Clemente IV (Cabral, 1998c).
A residência dos jesuítas era parte do conjunto formado pela capela, convento e colégio. Sofreu muitas reformas, o que acarretou a perda de suas características primitivas. (Nóbrega, 1982).
As principais reformas foram: em 1850, pelo coronel José Vicente de Amorim Bezerra; em 1858, pelo coronel Henrique de Beaurapaire Rohan e em 1858, pelo comendador Silvino Elvídio Carneiro da Cunha, conhecido como o Barão do Abiaí. Nesta época, o período Imperial, o prédio foi denominado Palácio da Presidência (Cabral, 1998c).
No local compreendido entre o convento, que fora transformado em palácio, e o colégio, onde hoje existe um jardim, se erguia a Capela de São Gonçalo. A Capela sofreu ampliações sendo denominada Igreja de Nossa Senhora da Conceição que desapareceu no ano de 1929, para dar lugar aos atuais jardins, durante o Governo de João Pessoa (Cabral, 1998c).
O nome Palácio da Redenção foi uma sugestão do povo em memória de uma manifestação de caráter coletivo ao Governo (Nóbrega, 1985).
