Sul luogo dell'attuaIe chiesa, al centro di un agglomerato di case malfamate, era stato edificato nel 1321 dai monaci della Badia fiorentina con finalita' rieducative, secondo un uso ricorrente nella chiesa primitiva, un oratorio intitolato a Santa Maria Madalena. Nel 1329 fu ceduto ai frati Celestini, i quali costruirono l'attuale chiesa in stile gotico a tre navate e campanile, la cui carnpana maggiore portava la data 1336. La chiesa di San Celestino, poi trasformata e dedicata a San Niccolo di Bari nel 1557 venne assegnata con l'annesso convento delle monache ospedaliere di San Giovanni di Gerusalemme affiliate all'ordine di Malta; in tale circostanza i celestini vennero trasferiti in San Michele Visdomini.
     Cosi' dette suore vennero ad abitare il convento di Via San Gallo ove rimasero fino alla soppressione del 1808. Presso la chiesa di San Niccolo e al convento delle gerosolimitane era sorto un piccolo ospedale della compagnia di San Giovanni Decollato, istituita dai "norcini", lavoranti di suini oriundi da Norcia, e poiche' la religione avevano per protettore San Giovanni Evangelista, derivo' una certa confusione tanto che, inizialmente, anche la loro chiesa venne chiamata San Giovanni Decollato ma poi prevalse il titolo di Sal Giovannino dei Cavalieri, dal nome dell'Evangelista protettore dei cavalieri di Malta.
     I locali dell'ex convento adiacente alla chiesa sono attualmente adibiti a scuola pubblica.
     La facciata della chiesa e' contrassegnata da un grande stemma coronato con la croce di Malta, la stessa che le monache portavano sull'abito nero dell'ordine agostiniano. Sulla stessa facciata e' apposta una lapide commemorativa in ricordo di marinai caduti in guerra, cio' in relazione al fatto che i cavalieri di Malta come quel￿li di Santo Stefano, aveva anche il compito della sorveglianza marittima.
     L'interno della chiesa che, dopo l'ultimo discusso restauro, si presenta nelle primitive forme trecentesche, e diviso in tre navate da ampie arcate a tutto sesto poste su pilastri a sezione quadrata ed e' preceduto da un vestibolo cinquecentesco sulle cui pareti sono gli armadi a muro originali nei quali i priori delI'ordine custodivano il loro archivio, le insegne e gli arredi.
     La navata centrale, piu' ampia di quelle laterali ha il tetto con capriate in vista. Le pregievoli cornici in pietra del primo altare delle navate laterali, eseguite nello stile di transizione tra Gotico e Rinascimento, sono attribuite a Piero di Giovanni Tedesco attivo a Firenze anche nell'Opera del Duomo, in Orsanmichele e a Santa Maria Novella. Ai lati della porta sono stati collocati il dipinto con la Nascita del Battista di santi di Tito e quello con la Decollazione del Battista eseguito da Pier Dandini provenienti dagli altari.
     Navata sinistra: al 1° altare Nativita' di Gesu' e predella raffigurante Circoncisione Santissima Trinito fra gli Angeli,
Adorazione dei Magi, di Lorenzo di Bicci (datato 1435);
addossato alla parte, Altare in marmi policromi del sec. XVIII, eseguito daII'Opificio delle Pietre Dure e proveniente dal presbiterio (1960);
sopra l'altare, Ultima Cena, attribuito a Jacopo Negretti detto Palma il Vecchio;
in testa alla navata, Incoronazione della Vergine e predella raffigurante i Santi Francesco, Girolamo, Pietro e le scene della Decollazione di Giovanni Battista e del ballo di Salome, Cristo risorto e il Miracolo di San Nicola di Bari, tavola di Neri di Bicci.
Abside: dietro l'altar maggiore, affresco raffigurante Paesaggio, di ignoto pittore fiorentino del sec. XVIII; Crocifisso fra due dolenti, tempera su tavola sagomata di Lorenzo Monaco (sec. XV), proveniente dalla chiesa di San Salvatore di Camaldoli;
Parete absidale sin. La Veronica asciuga iI volto di Gesu;
parete absidale destra Gesu nelI'orto del Getsemani, di ignoto pittore fiorentino del sec. XVIII
Cupola: L'Immacolata Concezione, affresco del sec. XVIII di Alessandro Gherardini e Rinaldo Botti.
Navata destra: in testa alla navata, Annunciazione, del Maestro di Stratonice (sec. XV)