Au XIIe siècle, à l'emplacement actuelle de l'église Sainte-Catherine, se trouvait - dit-on - une petite chapelle rattachée au château voisin des seigneurs de Mauléon. Cependant, les moines de l'abbaye cistercienne de Saint-Laurent à l'est (voir l'abbaye des Châteliers) et ceux de Saint-Martin à l'ouest suffisaient à la petite population locale. Lors de la guerre de Cent Ans, le bourg de la Flotte fut pillé de nombreuses fois et l'église a dû en souffrir. La restauration s'engagea dans la 2e moitié du XVe siècle.
Pendant les guerres de Religion, elle fut dévastée par les protestants en 1575, puis relevée par les habitants qui obtinrent d'Henri IV qu'elle devienne une paroisse et ne soit plus fille de la paroisse de Saint-Martin. En 1627, les Anglais occupèrent l'île et, au vu des documents d'époque portant trace de réparations, mirent à mal l'église. En 1741, elle est agrandie. En 1789, les Révolutionnaires volent les ornements et le mobilier (les statues avaient déjà été détruites par les huguenots). L'église Sainte-Catherine sera rendue au culte catholique un peu avant le Concordat de 1801.