Püha Risti kirik asus Paides juba keskajal. 1573. aastal lasid venelased Paide piiramisel kiriku õhku. Rootsi ajal rajati praeguse kiriku ette väike puukirik, mis põletati 1703. aastal koos linnaga maha.
1730. aastail rajati rootsiaegse puukiriku kohale vanasse kasvuhoonesse abikirik.
1767. alustati keskaegse kiriku müüridele uue hoone rajamist. Esmalt puhastati ja kaevati välja vundamendid. August Wilhelm Hupeli sõnul tulid mulla alt välja keskaegsed piidad, sambad ja hauakivid.
Kiriku ja torni müürid ehitati paekivist, kuid võlvimata lagi ja torni ülaosa olid puust. Paide kiriku torn ehitati mitte kiriku lääne-, vaid lõunaküljele. Seda seetõttu, et siduda linna turuväljak ja kirikuhoone ühtseks klassitsistlikuks tervikuks.
10. mail1845 Paide kirik põles. Kiriku taastamiseks korraldati korjandus. Annetustena saadi 10 480 rubla, millest 500 rubla annetas keiser Nikolai I.
2007.–2008. aasta Paide kirikus ning 2013. aastal kirikus ja kirikuaiasarheoloogVillu Kadaka juhtimisel toimunud välitööde käigus selgus, et praegune kirikuhoone on tõepoolest ehitatud 18. sajandi teisel poolel keskaegse kiriku alusmüüridele, nagu väitis juba August Wilhelm Hupel. 2013. aasta uurimistöö põhjal väitis Kadakas, et praeguse, 18. sajandi teisel poolel valminud kiriku pikihoone on tõepoolest püstitatud tunduvalt paksemate müüridega (kiriku põhiplaan umbes 22 × 31,5 m) keskaegse kiriku pikihoone alusmüüridele, aga üldjoontes on kiriku plaaniline kuju siiski rekonstrueeritav.[3]
Leitud tugipiilari jäänuste põhjal sai nüüd järeldada, et kirik oli jaotatud neljaks traveeks ning et hoone oli ilmselt võlvlaega. Tõenäoliselt oli kirik kolmelööviline, nagu ka enamik Järvamaa keskaegseid maakirikuid. Nelja travee puhul pidi järelikult kokku olema 12 võlvi, mida kandsid lisaks seintele neli piilarit. Selle ja tugipiilarite paigutuse põhjal võib järeldada, et võlve kandsid arvatavasti kuus ümarsammast.[3]
