Le prime notizie ufficiali su Melazzo datano 991 d.c.. In epoca romana il territorio era percorso da un cunicolo che portava le acque del torrente Erro all'acquedotto romano, di cui restano visibili tracce ad Acqui Terme. Nell'XI secolo Melazzo era feudo imperiale dei Conti d' Acquesana, come ricordano gli stemmi in ferro battuto agli ingressi. Nel 1004 nacque nel Castello il conte Guido, divenuto Vescovo di Acqui nel 1034 e dopo la sua morte, avvenuta nel 1070, proclamato Santo e protettore della diocesi di Acqui. Questi donò i propri diritti signorili alla chiesa di Acqui, la quale ne ottenne conferma del possesso nel 1039 e successivamente nel 1052 dall'imperatore Enrico III. Fu feudo della diocesi di Acqui verso il mille. Nel XIII secolo divenne possedimento dei marchesi del Bosco, i quali lo cedettero presto, rivendicandone però l'investitura, al comune di Alessandria.

Il Marchese del Bosco, occupandone il castello e le torri, causò dure ma inutili proteste da parte del centro acquese. Melazzo passò poi dalla Chiesa d'Acqui al Comune e successivamente ai Marchesi del Monferrato, fino ai saccheggi delle truppe di Francesco Sforza nel 1431. Nel 1500 troviamo signori di Melazzo la famiglia Falletti.

Il feudo fu poi comprato dal duca di Mantova e del Monferrato che lo diede ai Gandolfi, marchesi di Melazzo e di Ricaldone, la cui famiglia era molto legata alla Casa Savoia. Nel XVI secolo il castello fu distrutto dagli spagnoli e ricostruito successivamente dai Gandolfi.

Al lussuoso Castello di Melazzo è legata la storia e l'avventurosa vita del re Edoardo II Plantageneto, deposto re d'Inghilterra. 

Qui egli soggiornò per circa tre anni (1330 - 1333), come ricorda, nella galleria del Castello, una lapide posta dagli Arnaldi nel 1879 secondo la quale, dopo essere stato deposto dal figlio, non sarebbe stato ucciso nel castello di Berkeley nel 1327, ma avrebbe trovato rifugio in Italia trascorrendo a Melazzo parte dei suoi ultimi anni.

Costruito per ragioni di difesa e strategia militare data la sua posizione fondamentale sulla via del mare, il Castello fu molto ambito dalle autorità vescovili, dalla città di Acqui, da Alessandria e dai signori del luogo; a partire dal XIV secolo divenne residenza di nobili signori infeudati dai Marchesi del Monferrato che ne avevano giurisdizione.

La sua importanza strategica ha fatto sì che il Castello venisse riprodotto negli affreschi della galleria delle carte geografiche in Vaticano, volute da Papa Gregorio XIII nel 1580.

Nel Rinascimento il Castello fu di proprietà dei Conti Falletti; fu castellana di Melazzo la poetessa Eleonora della Croce, moglie del conte Giovan Giorgio Falletti, della illustre famiglia dei De La Revoire (al servizio del Duca di Savoia), che ne fece per lunghi anni un importante cenacolo di umanisti.