L'église du vieux bourg, entourée d'un cimetière, était dédiée à saint Paul. Elle était située à l'ouest du quartier de Bestaven, non loin du tuc de Houns, dans l'actuel lieudit Saint-Paul-le-vieux. Cette église est répertoriée dans la nomenclature des paroisses du Born de 1398 sous le nom de « Sanctus Paulus de Frontinhaco ». Ce nom de Saint Paul de Frontignan proviendrait du nom d'un propriétaire de l'époque gallo-romaine.
En 1678, il ne restait plus à l'emplacement de l'ancien bourg que l'église et « une petite maison où logeait le sacristain et sa famille ». L'église était d'ailleurs en « très pauvre état et menaçait ruine ». Les principaux habitants de la paroisse demandèrent à l'archevêque de Bordeaux le transfert à Saint-Michel de Paynsas. En juin de cette même année, l'archevêque fit effectuer une enquête. Le greffier dument mandaté indique que l'église paroissiale « n'est pas à plus de cent pas de l'étang et qu'elle est au milieu de marais ». « L'hiver, le pavé est tout couvert d'eau, si bien qu'on ne peut entendre le Saint Office que dans une posture qui n'est pas trop décente ». Par ordonnance du 28 septembre 1678, l'archevêque donne l'autorisation du transfert. C'est depuis cette date que l'église actuelle est devenue l'église paroissiale de Saint-Paul-en-Born.
Située à cinq kilomètres au sud du bourg, au quartier de Leych, elle était dédiée à saint-Jean de Jérusalem et appartenait aux chevaliers de Malte, qui était un ordre hospitalier. Elle a dû servir à accueillir les pèlerins de Saint-Jacques-de-Compostelle sur la voie de Soulac. On est sûr qu'elle existait encore en 1760, date à laquelle elle fut entièrement remaniée. « La pierre nécessaire est tirée de la lande proche par un carrier qui demande 18 sols par jour. La charpente est refaite, les murs sont blanchis et des ornements sont fournis par l'ordre de Malte et par Pierre Menaut ». Elle semble avoir disparu vers 1840 ou 1850.