A construção do castelo remonta a 1170, por determinação de D. Afonso Henriques (1112-1185). O primeiro documento, entretanto, a referir a povoação é a Carta de Foral que lhe foi passada pelo sobera
no em 1183 (e não 1181 como tem sido repetido em função de erro de transcrição), garantindo aos seus habitantes (por solicitação dos próprios) privilégios semelhantes aos que gozava o feudo galego de Ribadavia. A partir de então, a vila fronteiriça progrediu com rapidez, de tal forma que o primitivo castelo estaria concluído já no início do século XIII, dividindo-se os autores entre os anos de 1205 e de 1212, ano em que, juntamente com outras praças vizinhas, fez frente à invasão das forças do reino de Leão no contexto da disputa entre D. Afonso II (1211-1223) e suas irmãs. Contribuíram para esta campanha construtiva, além dos próprios habitantes e do apoio real, os recursos do Mosteiro de Longos Vales e do Mosteiro de Fiães.
O seu filho e sucessor, D. Sancho II (1223-1248) deixou a cargo do Concelho a nomeação do alcaide, privilégio que, D. Afonso III (1248-1279), ao conceder à vila, em 1258, um segundo foral, reivindicou novamente para a Coroa. A construção da cerca da vila, iniciada em 1245 e cujo troço oeste foi concluído em 1263, inscreveu-se numa grande campanha de obras empreendida por este soberano, que atualizou as defesas do castelo, uma vez mais com o apoio do Mosteiro de Fiães. A placa epigráfica no portão principal, assinalando este último ano, registra as identidades do responsável pelos trabalhos, o alcaide Martinho Gonçalves, e o seu arquiteto, Fernando, Mestre de Pedraria.
Em 1361 o trânsito entre Portugal e a Galiza deveria ser feito, obrigatoriamente, por Melgaço, dado revelador da sua importância, à época.
No contexto da crise de 1383-1385, a vila e seu castelo seguiram a tendência do norte de Portugal, mantendo o partido de D. Beatriz. No início de 1387, governados por um alcaide castelhano, sofreram o assédio das tropas portuguesas sob o comando de D. João I (1385-1433), vindo a cair ao fim de uma denodada resistência de quase dois meses.
Em 1492 Melgaço era um dos cinco únicos lugares da fronteira portuguesa facultados para ingresso dos judeus expulsos da Espanha (sefarditas). Ainda sob o reinado de D. Manuel, as defesas da vila e seu castelo encontram-se figuradas por Duarte de Armas (Livro das Fortalezas, c. 1509), integradas por três torres e duas portas.
No século XVII, no contexto da Guerra da Restauração da independência portuguesa, as defesas da vila sofreram obras de adaptação aos avanços da artilharia, recebendo linhas abaluartadas que envolveram o recinto medieval.
Encontra-se classificado como Monumento Nacional por Decreto publicado em 23 de Junho de 1910, tendo a muralha da vila sido classificada do mesmo modo, com publicação em 19 de Fevereiro de 1926.
A intervenção do poder público, entretanto, só veio a se fazer sentir na década de 1960, mantendo as características construtivas do conjunto. Recentemente, com o desenvolvimento de projetos de valorização do núcleo histórico da vila, a torre de menagem do castelo foi requalificada como núcleo museológico, expondo os testemunhos obtidos pela pesquisa arqueológica.