Foi a primeira fortificação iniciada no arquipélago, na passagem da década de 1460 para a de 1470, pelo fundador de Angra João Vaz Corte-Real e que posteriormente passaria aos domínios de Álvaro Martins Homem. Constituir-se-ia numa fortificação de modestas proporções, no local onde atualmente existe o monumento do Alto da Memória, em posição dominante sobre o vale, a ribeira e o porto da vila, ainda seguindo as concepções castrenses tardo-medievais: em lugar elevado, no interior da terra, afastado do mar. Pela encosta desta mesma elevação, fez correr artificialmente uma ribeira para, com a força das suas águas, mover as rodas dos moinhos que fez erguer em seu curso, e de que era o explorador exclusivo: a Ribeira dos Moinhos. Essa circunstância fez com que o local ficasse popularmente conhecido como "Alto dos Moinhos", e a sua fortificação como "Castelo dos Moinhos".
Embora esperasse receber a doação desses domínios, em 1474 foi-lhe doada a Capitania da Praia. O primeiro capitão do donatário da Capitania de Angra,João Vaz Corte-Real não encontrou razões para prosseguir a obra defensiva.
Anos mais tarde, a ilha foi atacada por marinheiros castelhanos, que desembarcaram inicialmente em Angra e depois na Praia. Por essa razão, em1482, a infanta Beatriz de Portugal, Duquesa de Viseu, que governava as ilhas em nome do Donatário, o seu filho D. Diogo, Duque de Beja e de Viseu, por carta a Álvaro Martins Homem, preveniu que embarcações castelhanas começavam a infestar os mares dos Açores, enviando à ilha Pedro Anes Rebelo, na qualidade de provedor das fortificações, para orientá-lo, enquanto capitão do donatário da Praia, no amuralhamento de sua vila. Anes Rebelo veio a desposar, na ilha, uma sobrinha da esposa de João Vaz Corte-Real, capitão do donatário de Angra, tendo concluído a construção do Castelo de São Cristóvão em 1493, de que terá sido o primeiro governador.
Em 1495, a alcaidaria-mor do castelo foi atribuída ao próprio capitão do donatário de Angra, que nele terá vivido algum tempo, nele colocando posteriormente pessoa de respeito, com soldo e título de Tenente, e com a obrigação de aí morar. A anexação da alcaidaria-mor do castelo à capitania, poderá explicar o nome de São Cristóvão, quando da construção do Castelo de São Filipe do Monte Brasil, sendo capitão do donatário o espanhol marquêsCristóvão de Moura.
Encontra-se representado na gravura "A Cidade de Angra na Ilha Iesu Xpo da Terceira que esta em 30 Graos", de Jan Huygen van Linschoten, datada de1595.
No contexto da Restauração da Independência de Portugal, a artilharia do Castelo de São Sebastião alvejou com êxito o Castelo de São Filipe, cercado pelas forças terceirenses. Perdida a sua função estratégica, as suas dependências foram utilizadas como Casa da Pólvora de Angra, que para ali foi transferida da Praça Velha, por razões de segurança.
O imóvel foi doado à Câmara Municipal de Angra em 1839, para dar lugar a umPasseio Público. Desse modo, em 20 de Maio de 1844, iniciou-se a demolição dos antigos muros, para a construção de um monumento em memória de D. Pedro IV, cuja pedra fundamental foi assentada em 3 de Março de 1845, declaradamente a mesma pedra em que o monarca primeiramente pisou, em igual dia e mês em 1832, ao desembarcar no cais de Angra.
