Etienne Lestrade figure parmi les témoins d'un hommage rendu au vicomte de Turenne en 1334, pour des biens situés dans le castrum et châtellenie de Floirac (T. Pataki, 1990). La tour elle-même est mentionnée en 1394 dans une lettre de Charles VI : elle appartient alors à Marguerite de Lestrade, seigneuresse de Floirac et d'Agude, à laquelle elle est rendue après avoir été occupée par des gens d'armes. En 1639, elle n'est cependant pas comprise dans les biens dénombrés par François de Lestrade, et semble être considérée comme un bien de la communauté, ce que confirmerait le fait qu'elle ne soit pas vendue comme Bien national à la Révolution. Elle est le siège de la justice seigneuriale au 18e siècle, l'auditoire se trouvant au premier étage et la prison au rez-de-chaussée (M. Carrière, J. Lamure, 1994, p. 247-248).
Les formes et la mise en oeuvre de l'appareil permettraient de la dater de la fin du 12e siècle ou de la première moitié du 13e siècle.