La première mention de ce castelnau remonte à 1293 dans le cartulaire de La Case-Dieu (Cursente, 1980). Un premier habitat se serait regroupé autour d'une église dans la vallée avant de s'installer sur la hauteur au 12e ou 13e siècle. En 1471, les consuls et conseillers se constituent en syndicat afin de procéder à des réparations sur la tour-porte et les murs du castelnau (AD Gers, I 3974, cité par Cursente). Le castelnau de Saint-Paul-de-Baïse est mentionné en 1483-1494 parmi les places fortes appartenant au comte d'Armagnac (AD Tarn-et-Garonne, A 46). La date de fondation de l'église auprès du castelnau n'est pas connue. L'emploi de moellons équarris identiques à ceux de la fortification villageoise en partie inférieure du clocher pourrait indiquer une construction ancienne. Cependant, il peut aussi s'agir de réemplois suite à la destruction d'une partie des fortifications et notamment de la tour porte en 1764 (AD Gers, C 576). Le document d'autorisation de démolition stipule en effet que les matériaux doivent servir à l'édification de l'église et du presbytère.