D'après les historiens, une église (ou une chapelle) est attestée à Scey-sur-Saône dès le 11e siècle. Elle a vraisemblablement subi d'importantes transformations ou reconstructions au fil des siècles. Les derniers travaux attestés datent de 1714 et concernent la transformation d'une ancienne sacristie en chapelle. Ce lieu de culte est desservi dans un premier temps par les curés des villages de Pont-lès-Traves et de Saint-Albin, qui sont successivement les chefs-lieux de la paroisse, avant l'érection de l'église de Scey en paroissiale. Au moment de la construction de l'édifice actuel, la paroisse réunit les villages de Scey-sur-Saône, La Neuvelle-lès-Scey (au nord) et Chassey-lès-Scey (au sud). Le contexte et la chronologie du chantier sont bien connus grâce aux recherches effectuées par Patrick Boisnard en vue du classement de l'édifice au titre des Monuments historiques (2011).

Construction de l'édifice actuel (1739-1759)

La paroisse reçoit l'autorisation de vendre une partie de son quart de réserve pour la reconstruction de son église par arrêté du Conseil du 8 juillet 1738. Les paroissiens choisissent le projet de l'architecte Jean-Pierre Galezot, qu'ils parviennent à imposer face à l'ingénieur des Ponts-et-Chaussées Jean Querret, commis dans un premier temps par le Grand Maître des Eaux et Forêts mais alors occupé en Lorraine. Le projet définitif est signé le 7 décembre 1738. La première pierre est posée le 20 juillet de l'année suivante. Les travaux sont adjugés pour un montant de 29.000 livres à François Lhéritier, entrepreneur à Scey-sur-Saône, qui s'associe à Jean Giulietti, appareilleur, et Jean Marpand, tailleur de pierre. Ils sont menés sous le contrôle du curé Jean-François Nobis. L'église est encore en chantier à la fin des années 1740. L'entrepreneur Nicolas Plaisonnet dit Lépine est chargé de l'achèvement des travaux de la nef en 1748. Le dallage de l'église est en cours en juin 1750. On ignore si le projet de Galezot (qui meurt en 1742) a été respecté pendant toute la durée du chantier. La tribune notamment pourrait avoir été ajoutée ultérieurement.

Lorsque débutent les travaux de construction du maître-autel et de décoration du chœur en 1750, l'église ne possède toujours pas de clocher. Le clocher hors-œuvre prévu par Galezot, qui aurait vraisemblablement dû prendre place à un angle de la façade occidentale, n'a pas été construit. Le rez-de-chaussée de la façade en revanche est percé en son centre d'un imposant portail donnant directement accès à la nef. L'architecte Hugues Faivre propose malgré tout un projet de clocher à construire au centre de cette façade occidentale. On en conserve le plan et l'élévation. Le projet initial est daté du 21 juillet 1755 mais il est modifié dès le 2 août et le 23 août, puis à nouveau au cours des mois suivants. Les travaux sont adjugés à l'architecte lui-même, pour un montant de 14.000 livres. Le portail déjà construit n'est pas détruit mais intégré dans le clocher-porche. La date de 1759 est inscrite au-dessus de la porte du clocher. L'église est consacrée en septembre 1761.

Travaux des 19e et 20e siècles

Divers travaux de réparations de toiture et de maçonnerie sont faits aux 19e et 20e siècles. Les toitures des chapelles latérales sont modifiées au moins à deux reprises. Elles sont dans un premier temps surélevées (architecte J. B. Bruand et entrepreneur C. É. Collet, 1812-1813). La couverture de lave est ensuite remplacée par des tuiles (entrepreneurs Varlet, Bouchu et Maréchal, 1873). Dans les années qui suivent, c'est la toiture du clocher qui est l'objet de travaux. Sa charpente est refaite par l'architecte J. Froissard en 1873. On conserve un document ("charpente actuelle du beffroi") en présentant le plan et la coupe. D'autres interventions au clocher sont attestées en 1881, 1897, 1923 et 1929. À l'intérieur, l'aménagement des deux calorifères successifs (1913 et 1937) entraînent des transformations dans la troisième chapelle latérale du bas-côté nord et la sacristie nord.

L'église est dans un état de délabrement avancé à l'arrivée de l'abbé Georges Demesmay (1885-1973) à la tête de la paroisse en 1928. Des travaux sont lancés par les communes copropriétaires dès l'année suivante, à l'extérieur (reprise des chéneaux) et surtout à l'intérieur (décapage des murs et des voûtes, pose d'un mortier et d'une couche de peinture sur les voûtes, réfection de l'installation électrique). Les murs et les piliers ont de nouveau été sablés plus récemment (seconde moitié du 20e siècle). Une plaque portant les noms des bienfaiteurs insignes en pierre de Beaune taillée par Georges Halley, sculpteur-marbrier de Vesoul, est posée dans la deuxième chapelle latérale du bas-côté sud en 1934.

Verrières des chapelles latérales et des fenêtres hautes

Les vitraux de plusieurs chapelles latérales datent de la fin du 19e siècle. Le vitrail de la première chapelle latérale nord porte la signature de la Maison C. Champigneulle, peintre-verrier de Bar-le-Duc, et la date de 1883. La signature figure également sur le vitrail de la troisième chapelle latérale sud (chapelle de Bauffremont). Le vitrail de la troisième chapelle latérale du bas-côté sud (chapelle des fonts baptismaux) est l'ancien vitrail de la deuxième chapelle latérale du bas-côté nord (chapelle Sainte-Anne). Il s'agit d'une grisaille à bordure de motifs végétaux colorés, déplacée à son emplacement actuel à la suite de la pose d'un nouveau vitrail dans la chapelle Sainte-Anne en 1932.

En octobre 1930, les huit vitraux des fenêtres hautes des bas-côtés surmontant les chapelles et sacristies sont installés. La série est divisée en deux groupes. Le premier est composé de quatre bustes de saints. Sainte Claire (au nord) fait face à saint Louis (au sud) dans la deuxième travée, et saint Henri (au nord) fait face à saint Georges (au sud) dans la quatrième travée. Les autres vitraux sont des scènes historiées. La Crucifixion (au sud) fait face aux "tombes du front" représentant des veuves et des orphelins (au nord) dans la troisième travée, et le Christ au milieu des enfants (au sud) fait face à sainte Thérèse de l'Enfant Jésus entourée d'anges (au nord). Ils sont exécutés par J. Benoît, peintre-verrier à Nancy.