La pieve di San Leolino ebbe origine probabilmente tra il X e il XI secolo ed era posta sulla strada che da Vallina porta a Fiesole. Tra i primi documenti che la ricordano si annovera l’atto di Donna Gilda, vedova di Azzo di Pagano, redatto nel 1066 a favore del monastero di San Pier Maggiore di Firenze. 
Si ricorda anche la bolla di Papa Pasquale II° che nel 1103 la conferma nella Diocesi di Fiesole al Vescovo Giovanni. Pochi anni dopo viene invece inserita nel dominio del Capitolo Metropolitano Fiorentino. Grazie alle proteste del Vescovo fiesolano la Pieve fu reinsediata nella Diocesi di Fiesole. Nel 1274 essa infatti è presente nel Decimario Vaticano come appartenente a quel vescovado. In quegli anni il piviere di San Leolino comprendeva una decina di chiese suffraganee. Dalla visita parrocchiale del 1436 sappiamo che il Signori di Caslellonchio erano i patroni della chiesa e che esercitarono tale ufficio fino al 1532 quando subentrarono le famiglie Venturi e Riccardi e la Pieve fu unita alla Chiesa Metropolitana di Firenze.
La chiesa è romanica, con la pianta a tre navate, tutte che si concludono con l’abside semicircolare, divise da quattro archi appoggiati a pilastri a sezione quadrangolare. L’impianto a basilica, i muri in alberese e pietraforte, le absidi semicircolari sono tipici dell’architettura romanica. La copertura è formata da capriate nell’aula centrale e da travi poste trasversalmente nelle navate laterali. Il campanile è stato costruito a partire dal XVI° secolo, sopraelevandolo in più volte.
Ristrutturata più volte durante i secoli, mantiene nella sola parte absidale il carattere originario, mentre la parte anteriore risulta modificata, probabilmente nel ‘700.
L’interno sobrio è rischiarato dalla presenza di alcune opere di rilievo, restaurate in occasione della riapertura della Pieve. E’ posto sull’altare di sinistra l’affresco con l’Incoronazione della Vergine, di scuola fiorentina, della fine del XIV secolo. Durante il restauro, lo stacco dell’affresco ha permesso il recupero, come elemento a se stante, della sinopia, All’altare di destra, è collocato l’affresco staccato rappresentante la Madonna che allatta il Bambino di Bicci di Lorenzo che, fino al 1797, era stato venerato nell’oratorio di Sezzano dei padri vallombrosani presso il Bombone, in località detta appunto “La Madonna”. 
Esiste nella chiesa anche un fonte battesimale del Cinquecento, in terracotta invetriata policroma, con le Storie di San Giovanni Battista, della bottega di Santi Buglioni. Di forma esagonale, esso è infatti costituito da sei scomparti, con scene della vita del Santo, divisi tra loro da doppi pilastrini ornati. L’alto basamento è sagomato, mentre, il coronamento, inizia con i capitelli dei pilastri e culmina con una serie di cornici aggettanti, decorate ad ovoli e dentelli.
Il 12 Luglio 2008 è stato festeggiato il Millenario della Pieve.
