Nel dipinto ad olio del 1749, che raffigura il Distretto parrocchiale di S.Nicolò all’Albergheria, custodito nel Museo Diocesano, è indicata con il nome di
S. Antonino ed il prospetto si affaccia su via Rosselli, parallela alla via Giuliano Mayali. La Compagnia di S. Antonio da Padova, comunemente detta di “ S. Antonino “ , venne costituita nel 1644 nel Convento dell’Annunziata, che sorgeva presso la Porta Mazara. Nel 1653 si trasferì nel Convento di S. Teresa al Trappetazzo, divenuto successivamente il Ritiro S. Pietro, ma fu costretto a lasciarlo nel 1666.
I Confrati acquistarono allora un magazzino in via Rosselli e lo adattarono ad Oratorio, dedicandolo a S. Antonio da Padova. Ma dopo qualche anno la Compagnia si estinse e l’Oratorio fu ceduto alla Maestranza dei “ macinatori di grano “, che dopo averlo abbattuto ne costruì al suo posto uno nuovo, dedicandolo alla Madonna del Paradiso.
Ciò avvenne il 1 Marzo 1762, come ricorda la lapide che ancora sovrasta l’originario ingresso nella via Rosselli.

La lapide riporta:

“ D. O. M.
L’ANNO DOMINO MDCCLXII PRIMO MARTY QVESTA VEN. LE
CHIESA E CONFRATERNITA DI MARIA SS. REGGINA DEL PARADISO DELLA
MAESTRANZA DEI MOLITORI FU ÆRETTA A PROPRIE SPESE DI DETTA
MAESTRANZA NEL GOVERNO DELL’ILL .MO E REVS PADRE DEP.TO CAN.
D. MARIANO MAURIGI CONSOLE M: ANTONIO BATILLARO ALE M. VINCENZO CORDARO CONSIG.
M.VINCENZO CAPVM M:GIOVANNI GIVLIANA RET.RE

Sino ai primi decenni del 1900 la via Giuliano Mayali ricadeva ad un livello superiore dietro il non più esistente Bastione di Porta S.Agata e con i lavori di risanamento del rione, avvenuti fra la fine del 1800 e l’inizio del secolo successivo, il Bastione fu demolito e venne creata la strada intitolata al Beato Giuliano Mayali, benedettino palermitano del 1400.
In questa circostanza i confrati, dopo aver murato il vecchio ingresso, costruirono una nuova facciata “ in stile “, dietro la quale si osserva il vecchio campanile della Chiesa. In conseguenza fu necessario ristrutturare anche l’interno dell’Oratorio, per cui oggi ben poco rimane dello stato originario.
Nel 1958 la Chiesa, affidata alla Confraternita di Maria SS. del Buon Rimedio, fondata nel 1642 circa e ricostituita nel 1923, è stata restaurata e riaperta al culto.