Il rustico del Convento e della Chiesa fu costruito da S. Francesco, aiutato dai milazzesi.S. Francesco nacque a Paola, in Calabria, nella Provincia di Cosenza, il 27 marzo 1416; fondò l'Ordine dei Frati Minimi nel 1435; Papa Giulio II il 28 luglio 1506 approvò le. Regole del I, del II e del III Ordine.
Nel 1464 viveva, esiliato a Paola, il milazzese Bernardo Caponi; questi fu talmente conquistato dalla santità di Frate Francesco che consigliò i Capi della Università (Comune) di invitare il Santo Frate a Milazzo. L'Università aderì al consiglio ed inviò due Magistrati: Angelo Camarda e Giovanni Villani ad invitare il Santo a Milazzo. Egli accettò volentieri. Accompagnato da due Frati: P. Paolo Rendacio e Fra Giovanni da S. Lucido, partì da Paterno Calabro, ove allora si trovava. Il 3 aprile 1464 arrivò a Catona, dalla cui spiaggia stava salpando per Messina, con un carico di legna, il barcaiolo Pietro Colosi. Frate Francesco lo pregò di traghettare anche lui ed i suoi due Frati, ma «per carità», perché non avevano denaro. Il barcaiolo Colosi si rifiutò e disse: «Voi non avete i soldi, ed io non ho la barca». S. Francesco non si perse d'animo: pregò il Signore, distese il suo mantello sulle acque, vi salì lui, vi fece salire gli altri, e partì alla volta di Messina. Attraversato lo Stretto sul mantello, approdò con i suoi sulla costa messinese, probabilmente nei pressi di Faro; quindi si incamminò per Milazzo. Trascorse la notte tra il 3 ed il 4 aprile in una abitazione dei Raffa, a Gesso; il 4 aprile 1464 raggiunse Milazzo.
L'Università e la cittadinanza lo accolsero con grandi onori. I responsabili della Città gli offrirono il Colle S. Biagio, perché vi costruisse un suo Convento ed una sua Chiesa. Il Santo accettò, ringraziò ed iniziò i due lavori di costruzione il 17 gennaio 1465. Molte Famiglie Patrizie fecero a gara nell'offrirgli una dimora, ove trascorrere la notte, ma egli preferì dormire con i poveri, ed elesse l'ospedaletto cittadino.
Poiché i muratori abbisognavano dell'acqua, S. Francesco indicò loro dove scavare per ottenere un pozzo; scavando, però, incontrarono due massi, a breve distanza l'uno dall'altro; intervenne il Santo, il quale, tracciato un segno di croce su ognuno, li alleggerì; egli stesso li pose in un luogo, sulla nuda terra; su essi innalzò una parete della Chiesa, e precisò: «Questi massi faranno da fondamenta per il Convento e per la Chiesa». Esistono ancora: sono recintati da sbarre profetizzò: «Quando i miei Figli si saranno provveduti di una cisterna per raccogliere acqua piovana, quest'acqua tornerà salmastra»: ciò, che realmente avvenne, quando i Frati della prima Comunità Religiosa si fecero la cisterna. L'acqua è tuttora salmastra; il pozzo sta nell'atrio della Caserma dei Carabinieri.
Per coprire la volta della Chiesa, S. Francesco faceva venire le travi da S. Pier Niceto; una trave risultò più corta, per cui non poteva poggiare sulle due pareti; ne fu informato; si fece indicare la trave, la prese tra le mani e la tirò, allungandola fino a che potesse poggiare sulle due pareti; il posto ove fu collocata questa trave è indicato da una lampadina sempre accesa; è la terza, entrando in Chiesa.
In poco più di tre anni, il Frate santo terminò sia il rustico del Convento che quello della Chiesa. Queste due costruzioni, che procedevano simultaneamente, sono senza fondamenta. S. Francesco volle che il Convento si chiamasse «Convento Gesù Maria», e la Chiesa «Chiesa Gesù Maria», anche se ora vengano chiamati «Convento S. Francesco di Paola) e «Santuario S. Francesco di Paola». Con gli anni, i Frati ingrandirono il Convento. Essi possedevano e coltivavano un grande orto. Nel 1620, circa, il Convento di Milazzo divenne Casa di Noviziato della Provincia Monastica di Messina; nello stesso anno, si ingrandì la Chiesa, che subì anche delle modifiche: la facciata e l'ingresso principale ven­nero spostati da ponente a oriente; l'altare maggiore subì lo steso spostamento; vi si aggiunse l'attuale presbiterio.
Per le vicende storiche del .1860 (soppressione degli Ordini Religiosi ed incameramento di tutti i beni ecclesiastici da parte dello Stato), anche i nostri Frati furono espulsi dal Convento, fu tolta loro la Chiesa, fu tolto loro l'orto. Tuttavia, come Rettore della Chiesa, rimase P. Giuseppe Piraino, il quale, con Breve Apostolico del 9 aprile 1817 era stato insignito del solo «titolo» di Generale dell'ordine da PAPA PIO VII (Atti Capitoli Generali, VoI. 2, p. 326, nota 1). Nell'orto, furono costruite le Scuole Medie Garibaldi; nella parte orientale del Convento si insediarono altre Scuole (ora c'è l'Istituto d'Arte); in quella occidentale, posero la Caserma dei Carabinieri. Dal 1909 al 1910 custode e Rettore della Chiesa fu P. Benedetto Nastasi. Nel 1908, nella notte dopo la Festa del S. Padre, la Chiesa si incendiò; molti affreschi si persero per sempre.
Nel 1823 il Convento di Milazzo fu scelto e designato dalla Curia Provincializia di Messina a «secondo Collegio per gli studenti della gioventù Minima», perché quello di Messina, 10° Collegio, non poteva contenere altri studenti. I Frati di Milazzo si distinsero sempre per virtù e per solida dottrina.
I Frati Minimi tornarono ufficialmente a Milazzo nel 1910. Il Comune cedette loro, in uso, la Chiesa e pochissimi vani, anche essi in uso soltanto.La Chiesa ha Personalità Giuridica riconosciuta con R. D. il 4 ottobre 1934, n: 1859; anche il Convento, ai sensi del Regio Decreto del 4 ottobre 1934, fu riconosciuto civilmente e, insieme alla Chiesa, fu registrato alla Corte dei Conti il 7 novembre 1934.
Nel 1507 il Convento già aveva una Comunità numerosa e molto osservante. Al 1° Capitolo Generale dell'Ordine, tenutosi al Pincio, a Roma, nel Convento della SS. Trinità, il 28 dicembre 1507, parteciparono anche due Frati di Milazzo: il Superiore P. Roberto e P. Stefano da S. Agata.
Il Vicario Correttore (Superiore) della prima Comunità fu P. Francesco Maiorana.