La fondazione del Santuario si fa risalire al 1444, ma tale data non è suffragata dalle fonti storiche del tempo. Tre dati cronologici. sufficienti per stabilire il tempo della costruzione della Chiesa e del Monastero, si evincono da alcune testimonianze rese durante il processo di canonizzazione del Taumaturgo:
a) la costruzione del Monastero non potè essere iniziata prima del 1472 perchè in quell'anno San Francesco venne da Paola a Paterno per la scelta del suolo sul quale doveva sorgere il Monastero.
b) la fabbrica non si protrasse, certamente, per un trentennio, sia per l'abbondanza dei prodigi operati dal Santo e sia per la presenza, nel cantiere, di un centinaio di operai;
c) la costruzione della chiesa cominciò o verso il 1472 assieme all'antico romitorio o qualche anno prima.
E' certo die i lavori della chiesa furono condotti a termine verso il 1480 mentre quelli del monastero continuarono fino al 1483. Comunque la chiesa e il romitorio di Paterno furono costruiti dopo il convento di Paola, ma, senz'altro, prima dei conventi di Spezzano e Corigliano.

Ai lavori presero parte numerosi uomini e donne del paese ed anche molti artigiani dei paesi vicini. La costruzione procedeva con grande fervore e, nel momento in cui bisognava collocare l'architrave sul portale,ccadde un evento prodigioso: l'architrave, per intervento del demonio. si spezzò in tre parti, ma il taumaturgo prese i tre pezzi in una sola volta e li collocò sullo stipite. Ancora oggi. dopo molti secoli, l'architrave perdura immobile. Sono chiaramente visibili sul frontespizio delle iscrizioni che rimandano alla data di costruzione della chiesa: il nome Jesus su una prima riga, due date con le prime due cifre in comune e le altre accavallate 1 4 47 47 sulla seconda riga e la sigla S F D P sulla terza.
Secondo P. Michele Stea. autore della monografia "11 Santuario di Paterno Calabro". la sigla potrebbe essere così interpretata: Sedes Fundata Dei Parenti cioè tempio innalzato alla Madre di Dio. Il numero potrebbe essere scomposto in due. 1444 e 1477, indicanti gli anni di inizio e di fine lavoro.

Ma l'osservazione più attenta dell'iscrizione ha portato ad una scoperta ed a conclusioni diverse:
1. la parola Jesus e le lettere S F D P furono rifatte in un secondo tempo sulle lettere incise in precedenza a caratteri corsivi:
2. la prima iscrizione fu fatta nel tempo in cui nella lunetta del portale fu dipinto l'affresco di S. Francesco (1520):
3. più tardi, probabilmente verso la seconda metà del 500. furono rifatte le lettere del nome Jesus e della sigla e, tra una riga e l'altra, fu inserito un numero indicante i due anni in cui si riteneva che fossero iniziati e finiti i lavori.
La sigla viene quindi così interpretata: Sanctus Franciscus de Pania. Ancora oggi resta irrisolto l'enigma dell'architrave del Santuario di Paterno. La chiesa ha per prospetto un portico a due piani con due ampi archi nella parte inferiore e con sei piccoli archi nella parte superiore.

L'interno della chiesa è stato restaurato nel secolo scorso: si presenta in duenavate, dove si trovavano gli altari dei vari Santi e l'altare maggiore.
Le pale degli altari risalgono al 700. Opere di pregevole fattura sono il tronetto del Presbiterio, il coro, il soffitto a cassettoni della Sacrestia, il lavabo in pietra e la nicchia delle reliquie in noce intarsiata. In quest'ultima si conservano, oltre al busto ligneo del Santo, un ossicino di San Francesco, un cappuccio, una funicella, i calzari in stoffa del Santo, due codici liturgici del XIII sec. usati dal Santo, la pelle della trota risuscitata, la pentola metallica e una delle due pietre sulle quali il Santo, partendo per la Francia, lasciò impresse le orme dei suoi piedi. Il portale del Santuario e archiacuto e il chiostro, in tufo, ad arcate gotiche con lunette istoriate nell'800.

La loggia che sovrasta l' ingresso e a quattro archi tondi; il campanile, fu eretto. probabilmente, nella seconda meta del 500; la cella campanaria e dotata di quattro campane e, sotto di essa. si può osservare un orologio pubblico fattovi collocare per voto da un emigrato all'inizio del secolo scorso.
I luoghi del Santuario, richiamanti il gusto artistico dei visitatori, oltre la Chiesa, sono il Refettorio e il Chiostro. Il Refettorio è una vasta sala. tramezzata da due file di colonne corinzie ottagonali, collegate con archi che sostengono il soffitto, rivestito di tavole arabescate: sulla parete di fondo, vi e un grandioso affresco dell'Ultima Cena" del 500 .
Ii chiostro, luminoso e armonioso, di figura quadrangolare, ha per ogni lato, sei arcate ogivali, che poggiano su altrettante colonne.
Nel centro, spartito ad aiole, vi era l'antico pozzo, che raccoglieva le acque piovane dei tetti del Convento e da qualche anno, è stato riempito

di pietre e sostituito con una vasca con pesci. Nei corridoi  vi sono 31 lunette, otto per ogni singola parete interna, tranne quella dove c'è il portone d'ingresso, con affreschi del '600 , raffiguranti alcuni miracoli di S. Francesco a Paterno ed episodi della sua vita. Esse hanno costituito il libro facile da leggere sulla vita del più  grande dei calabresi di tutti i tempi: S. Francesco di Paola.
Pur necessitando di un urgente restauro da parte di coloro che hanno il compito di conservare il patrimonio della nostra cultura calabrese, esse continuano a parlare al nostro cuore e a testimoniarci l'opera meravigliosa del Santo.