Depuis l'époque médiévale, Vauchoux fait partie de la paroisse de Scye. Néanmoins, en 1844, la commune souhaite se doter d'un édifice religieux sur son territoire.

Le conseil municipal a décidé d'implanter l'église à l’emplacement du four banal situé sur la place publique en haut du village. La commune fait appel à Dodelier, architecte à Vesoul en 1844. Il rédige une version du projet sous la forme d'un devis descriptif. L'édifice sera construit principalement avec les calcaires provenant de la carrière locale. Le projet initial prévoit en plus, des tuiles vernissées pour le toit du clocher. Ce document est complété par un devis estimatif s'élevant 25 800 francs. L'architecte remet ce projet à la mairie de Vauchoux le 25 juillet 1844. Le conseil municipal valide l'édifice imaginé par l'architecte. Le 8 octobre 1844, la préfecture émet un avis favorable mais rappelle à l'équipe municipale que la commune devra avoir les ressources financières nécessaires pour meubler l'église, construire un cimetière et un presbytère et assurer le traitement du prêtre. Ces conditions sont imposées par l'autorité diocésaine. Dodelier livre à la commune les plans de la chapelle le 25 février 1846, conformément au devis descriptif rédigé. Ils sont approuvés par la préfecture le 26 mars 1846.

L’accord final de la préfecture permet à la commune d’engager la procédure d’achat du four situé sur la place publique. L’acquisition est faite par la commune pour la somme de 700 francs au cours de l’été 1847. L’administration municipale en profite pour revoir l’orientation de l’église ; en effet, elle désire que l’édifice soit dans l’axe de la Grande Rue.

Une délibération du conseil municipal du 9 novembre validée par la préfecture le 25 du même mois autorise la commune à prévoir avec l’architecte des travaux supplémentaires. Ils portent sur la nécessité de construire l'édifice sur un socle en pierre de taille pour empêcher l’humidité, suite à son changement d’orientation, la construction d’un beffroi avec une charpente en bois, des fenêtres au clocher et le lambrissage de la toiture. Le montant de ces travaux proposé par Dodelier le 15 janvier 1848, s’élèvent à 1 550 francs. Les travaux sont mis en adjudication en juillet 1847 et débutent en 1848. L’architecte propose au conseil municipal un projet de décoration et d’ameublement de la future église (devis descriptif du 17 juin 1848 se montant à 7 500 francs et plans de la disposition du décor). L’adjudication de la fourniture de la cloche, qui pèsera environ 600 kilogrammes est réalisée le 10 février avec pour obligation d’être livrée pour le 15 mai. La construction de l'église est achevée en fin d'année.

En 1901, le conseil municipal se met en relation avec une société d'horlogerie (Paul Odobey et fils, manufacture basée à Morez dans le Jura) pour équiper l'église d'une horloge qui sera installée sur la tour du clocher. Suite à la visite d'un employé de la société à Vauchoux, la société envoie au maire, le 25 juillet 1901, un devis pour installer le cadran. Celui-ci s’élève à 1 770 francs, incluant une garantie de 10 ans et le transport jusqu'à Port-sur-Saône, le reste du trajet étant à la charge de la commune. La manufacture s'engage pour une mise en place le 1er octobre 1901.

En 1920, des travaux d'entretiens sont effectués à l'église, sous la responsabilité de l'architecte Humbaire ; ils consistent principalement à remplacer des plaques de tôles galvanisés sur le clocher et de petites tuiles sur le nef.