Construit directement sur un promontoire aux confins de la Haute Auvergne et du Rouergue, dans une situation de marche frontière, il se composait d'un donjon d'architecture romane classique du Moyen Âge (le donjon Ouest actuel), entouré d'une enceinte elle-même formée d'une muraille flanquée de cinq à sept tours de défense dont il ne reste aujourd'hui qu'une tour carrée d'origine au sud-est et une tour modifiée et surélevée au nord-ouest (dite tour de l'oubliette).
A l'intérieur de l'enceinte, une douve sèche entourait donc le donjon et quelques bâtiments communs de faible hauteur destinés à l'hébergement des domestiques et des gens d'armes. Ce donjon ancien comportait sans doute trois niveaux dont l'un pour le seigneur et le plus élevé pour la surveillance de la vallée du Goul. L'emplacement de Messilhac était en effet stratégique car la vallée du Goul, l'une des huit vallées qui trouvent leur origine au Plomb du Cantal, était une voie de pénétration aisée de la Haute Auvergne par le sud. Sur les deux versants de cette vallée, quelques autres châteaux coexistèrent avec Messilhac dont il ne reste plus de nos jours que le château de Cropières et la tour de Puechmouriez situés en amont sur la rive gauche du Goul.
Un village aurait existé aux pieds du château, sur le bord de la rivière, dont il ne reste plus de traces aujourd'hui.
Le château aurait été construit par un membre de la famille de Bénavent qui aurait passé la Truyère et serait venu se fixer à Messilhac pour une raison encore inconnue. La famille de Bénavent est une famille rouergate, branche de la maison de Rodez qui détenait la vicomté de Carlat. Un rameau de la famille de Bénavent aurait plus tard traversé le Goul et construit, face à Messilhac sur la rive droite à Cros-de-Ronesque, un autre château, Montamat, dont il ne reste plus même les ruines.
Montamat et Messilhac auraient ensuite appartenu au même seigneur, vassal du seigneur de Carlat.
Des transformations importantes furent réalisées au XIVe siècle avec la construction de la tour Est de style gothique avec ses pièces voûtées à la différence de celles du donjon Ouest qui comportent des plafonds plats. Le bâtiment central fut sans doute construit à cette époque également. Mais sa façade, exposée au sud était percée seulement de meurtrières pour la défense du château. L'entrée du château située au Nord, à mi-étage était sans doute protégée par un pont levis en bois. L'escalier central à vis permettait de desservir l'ensemble du château ; il montait vers la droite pour permettre aux habitants du château de se défendre quand ils étaient attaqués par des assaillants montant vers eux. Les pièces du rez de chaussée étaient les écuries ( la salle à manger actuelle ), la sellerie (dans le donjon Ouest ), et les cuisines dans la partie Est.
On peut encore remarquer aujourd'hui sur cette façade Nord l'entourage en pierres taillées de l'ancienne porte d'entrée ainsi que celui d'une ancienne ouverture juste au-dessus. C'est sans doute également aux alentours du XIVe siècle que le donjon Ouest, dans un souci de symétrie et d'efficacité militaire fut surélevé d'un ou deux niveaux et muni des mêmes mâchicoulis que la tour Est. L'ancien oratoire, situé en son cinquième niveau, voûté et de style gothique en témoigne. Un chemin de ronde existait alors de part et d'autre du corps central, sur les façades sud et nord ; seuls en restent aujourd'hui une petite partie au Nord et les corbeaux qui le soutenaient au Sud.
Les transformations les plus remarquables furent ensuite réalisées au début du XVIe siècle ( la date de 1531 se trouve gravée sur une des pierres de la façade ) quand le calme revint dans la région après les nombreuses guerres qui marquèrent la France jusqu'à François Ier.
Jean de Montamat fit ouvrir la façade sud de nombreuses fenêtres à meneaux, la fit orner de sculptures du style de la Renaissance sur toute la hauteur du bâtiment autour et au-dessus de ce qui devint alors la porte d'entrée du château et remplaça l'ancien escalier à vis par un escalier droit en pierre de style italien qui dessert aujourd'hui les deux premiers étages de l'édifice. La construction de ce nouvel escalier s'accompagna de la création d'un vestibule de style gothique flamboyant avec de nombreuses ogives reposant sur des " culs de lampes " richement sculptés.
Un dernier ajout fut réalisé à la fin du XVIIIe siècle par la construction de l'aile dite moderne au Nord qui s'appuie sur l'ancienne enceinte de défense qui constitue de nos jours le mur extérieur du château au Nord.
Une partie de l'enceinte en ruine, fut rasée à la fin du XIXe siècle ; ses pierres furent utilisées pour la construction du mur de soutènement de la terrasse est. Au début du vingtième siècle, le reste de l'enceinte fut mis à niveau et la terrasse actuelle dégagée du bâtiment qui avait été construit sur sa partie Ouest