Es tracta de la primitiva parròquia de Valls, un dels dos centres, juntament amb el castell, de la vila medieval. La primera notícia segura sobre l’església parroquial de Sant Joan de Valls és de l’any 1194, en què consta entre les parròquies que el papa Celestí III va confirmar a l’arquebisbe de Tarragona en la butlla que li atorgà l’esmentat any. Tot el que sobre Valls i el seu origen diuen Francesc Puigjaner i altres autors no té cap validesa històrica i no supera cap anàlisi crítica moderna. De moment és encara difícil fer hipòtesis sobre l’origen de la parròquia, que certament ha de ser posterior al 1155.
De seguida, la parròquia de Sant Joan de Valls esdevingué una de les més importants del Camp de Tarragona, com ho proven les relacions de les dècimes papals dels anys 1279 i 1280. El rector de Valls hi contribuí amb 444 sous i 3 diners, el primer any, i amb 473 sous i 6 diners, el segon.
L’església parroquial de Valls, cap al final del segle XV, era de col·lació de l’ardiaca major. A mitjan segle XVIII n’eren esglésies sufragànies les de Picamoixons, Fontscaldes, Masmolets i la Granja.
L’edifici romànic ha desaparegut del tot. A mitjan segle XIV fou reedificat i probablement ampliat per manament de l’arquebisbe de Tarragona. Al segle XVI, davant la insuficiència de l’església parroquial que impedia a tots els veïns l’assistència als oficis els dies de festa, hom decidí de bastir un nou temple, l’actual. El 5 de maig de 1565 es nomenà una comissió perquè anés a Barcelona a veure quin model d’església era l’adequat per a la vila. El 29 de juny del mateix any la comissió declarà que es decantava per seguir el model de Sant Agustí el Vell, de Barcelona. El 15 d’agost de l’any 1569 es feu la subhasta de les obres que foren adjudicades als mestres de Barcelona, Bartomeu Roig, pare i fill, per 21 000 lliures. El 10 de setembre del mateix any començaren a obrir-se els fonaments. L’obra sembla que acabà al març del 1583.
Entre els nombrosos altars destruïts l’any 1936, destaca el retaule de l’altar major, en part conservat, que fou construït pels germans Josep i Llàtzer Tremulles entre 1639 i 1662.