La 1ère édification remonte au XIème siècle dont il ne reste aujourd'hui que la base de l'imposant donjon. 

Au cour du XIIème siècle, les "Henriciens" (secte manichéenne suivant les préceptes d'Henri de Lausanne) fuyant les soldats vinrent se réfugier à Gavaudun.

Pendant des decennies, ils vont être reconnus comme de véritables brigands redoutés de tous, pillant les récoltes. En 1165, Jean d'Assida, évêque de Périgueux, assiège le château, il prive les hérétiques d'eau et de vivre, les obligeant à se rendre. Pour symboliser sa victoire, il fait raser le château. La légende raconte que ces bandits avaient amassés un important trésor durant ces années de pillages mais personne n'a encore trouvé le butin.

Il faudra attendre le début du XIII° siècle pour que la forteresse soit relevée de ses ruines par Almustang de Valens (ou Balenx).

Lorsque Raymond Bernard de Valens donne sa fille en mariage à Jean 1° de Durfort, nous sommes à l'aube de la guerre de Cent Ans, l'Aquitaine est alors en grande partie une province anglaise où peu de seigneurs soutiennent le Roi de France.

Mais Jean 1° de Durfort offre son épée à la couronne de France et s'empare en 1372 de la bastide anglaise de Monflanquin qu'il place sous l'autorité de Charles V. Gavaudun devient ainsi la "bête noire" du parti anglais.

Le dernier Durfort à porter le titre de seigneur de Gavaudun est Jean II de Durfort. Tout comme ses prédécesseur il se range du côté de la france, ce qui lui vaut l'estime de Charles VII et du Comte de Foix au côté duquel il se bat. 

Privé de descendance mâle, il donne sa fille en mariage à Arnaud dit Naudonnet de Lustrac, un des plus illustre capitaine de l'agenais redouté des anglais par ses coups de maître, il sera fait sénéchal de l'agenais en 1437. 

Parmi la descendance des Lustrac, nous trouvons en 1527 Marguerite de Lustrac, fille d'Antoine II de Lustrac et de Gavaudun et de Françoise de Pompadour.A la mort de son père, elle hérite du château et se retrouve à la tête d’une des plus grandes fortunes du royaume.

Dotée d’une grande beauté et dévorante d’ambition, sa vie sera riche en rebondissements.

En 1544, Marguerite de Lustrac épouse Jacques d'Albon de saint André, alors capitaine des ordonnances du Roi François 1er.

Aprés le décés de son époux, elle épouse en seconde noce Geoffroy de Caumont, un seigneur protestant,qui sera empoisonné en 1574 par les frères Commarque. 

Marguerite est alors enceinte de sept mois, la sachant seule, ses ennemies se sont emparées de ses terres .Elle en appelle à la reine, Catherine de Médicis, qui refuse de l’aider. Elle se tourne alors vers Henri de Navarre, chef des huguenots, (futur roi Henri IV) qui lui offre aide et protection ; il lui envoie son plus illustre capitaine, Geoffroy de Vivans qui très vite chasse ses ennemies et lui remet ses terres. (On raconte qu'à Libos il a traversé le lot à la nage sous le feu des catholiques, que lors de la bataille de Coutras en 1587, blessé au ventre il ne rompt pas le combat pour laisser le temps à Henri de Navarre d'arriver et de remporter la victoire. C'est à Gavaudun qu'il fait sa convalescence mais très vite repart au combat. Il meurt en 1590 au siège de Villandraut.) 

Peu après Margueritte se retire dans sa résidence des Milandes et lègue sa terre à sa fille Anne de Caumont (future épouse de François d'Orléans) qui hérite du castel ainsi que des paroisses de Laurenque, Salles et Vauris. 

A la mort d’Anne de Caumont, c’est la famille d’Auray de Brie qui devient propriétaire du château jusqu’au jour où l’un des membres de la famille, favori à la cour de Louis XIV, perde ses terres au jeu.

Ainsi, en 1690, par adjudication, le château devient la propriété du Marquis de Belsunce (le dernier des Belsunce était surnommé le tueur de loups encore nombreux dans nos bois) jusqu’à l’approche de la révolution, période où il appartient à Philibert de Fumel-Monségur, émigré de la révolution.  Puis il sera vendu en qualité de bien national au sieur Pierre Fort, marchand de Gavaudun. 

Celui-ci, au début du XIX° siècle, cédera le château à la commune de Gavaudun dans un état de ruine avancé.