Tem como origem uma capela construída sobre as ruínas do fortin de Santa Cruz (século XVII). Em 1623, estando o mesmo em condições precárias e sem função estratégica, os militares pedem a Martim Correia de Sá, governador da época, permissão para construção de uma capela e um cemitério. Assim, teriam onde rezar e enterrar os seus mortos. A permissão é concedida e, cinco anos depois, em 1628, a capela é inaugurada com o nome de Capela de Santa Vera Cruz, com devoção à Santa de mesmo nome.

Serviu duas vezes como catedral, de 1703 a 1704 e de 1734 a 1737, quando a igreja de São Sebastião (Catedral da Sé), no Morro do Castelo, encontrava-se em condições precárias.

Necessitando de reformas, em 1780, inicia-se a construção de uma nova igreja (a atual), já com o nome de Igreja de Santa Cruz dos Militares. As obras terminam somente em 1811 (31 anos após). É sagrada a 28 de outubro de 1811, com a invocação de “Santa Cruz”, na presença de D.João VI, então príncipe regente.

Em 1840 um incêndio destrói quase toda a decoração interior feita pelo Mestre Valentim. Mestre Antônio de Pádua e Castro, em 1870, reforma o interior fazendo uma nova decoração e aproveitando tudo o que sobrou. Em 1914, uma nova reforma modifica o interior.