Generalment es considera que la primera referència a aquesta església, actual parròquia de Vinyols, és del 1246, en què Pere d’Albalat, arquebisbe de Tarragona i senyor del lloc, atorgà carta de franqueses als habitants de Vinyols. D’aquest document en tenim notícia gràcies a un breu resum que en feu el canonge J. Blanch al segle XVII. Segons J. Blanch, entre les concessions atorgades, hi havia la que els “habitants y naturals de Vinyols, que aleshores se anave poblant y avien de anar los dies de festa a ohir missa a la Iglesia del terme dels Archs, que puguessen fer una iglesia en dit lloc sots invocació de santa Caterina, ab pacte, empero, que fos suffraganea de la dita iglesia dels Archs”. Aquest permís per a bastir una església a Vinyols no sembla concordar amb el fet que tant en el testament de Bernat dels Arcs del 1227 com en el de Pere dels Arcs del 1243 es facin donacions a l’església de Santa Caterina dels Arcs, que bé podria correspondre a l’actual Santa Caterina de Vinyols.
L’església de Vinyols fou en un principi sufragània de la parròquia de Sant Joan dels Arcs. Ambdues esglésies al final del segle XV eren de col·lació de l’arquebisbe. El despoblament dels Arcs cap al final de l’edat mitjana i el progressiu creixement de Vinyols feu que a la segona meitat del segle XVI la situació s’hagués invertit en benefici de Santa Caterina de Vinyols i que aquesta església s’hagués convertit en parròquia del terme. Durant el mateix segle XVI l’església de Vinyols fou unida a la lectoría de la catedral de Tarragona. A la primera meitat del segle XVIII figura com a vicaria perpètua, amb l’església dels Arcs com a sufragània.
El temple actual és barroc amb decoració rococó i, segons una inscripció de la façana, data del 1778.