L'origine dell'edificio risale al 1028, quando il vescovo Jacopo il Bavaro decise di trasferire la cattedrale, che era fino ad allora presso la Badia, entro le mura della città, dedicandola a san Romolo, evangelizzatore di Fiesole.

Fu ampliato nel Duecento, come ricorda un'iscrizione datata 1260 sulla quinta colonna della navata destra, e ancora nel Trecento da Andrea Corsini. Nuove trasformazioni e abbellimenti si ebbero nei secoli successivi, finché nel 1878-1883 con finanziamento statale venne effettuato un radicale restauro, curato dal Genio Civile di Firenze, che comportò la ricostruzione integrale della facciata. Il campanile risale al 1213, ma fu rifatto nel Settecento e nel 1739 venne dotato di coronamento con merlatura sporgente.

La cappella sepolcrale del vescovo Leonardo Salutati è il gioiello rinascimentale del Duomo e ospita il monumento funebre del vescovo (1466) in forma di sarcofago in marmo finemente scolpito da Mino da Fiesole e lumeggiato d'oro, che reca al di sotto, sopra una mensola, un busto-ritratto particolarmente realistico. Alla parete di fronte è situato un dossale marmoreo con la Madonna in adorazione del Bambino tra San Leonardo e San Remigio, coronato da una bellissima testa del Salvatore. Entrambe le opere sono firmate Opus Mini. In armonia con questi rilievi fu eseguita contemporaneamente da Cosimo Rosselli la decorazione pittorica condotta a tappeto su pareti e soffitto con le raffigurazioni degli Evangelisti e dei Santi Leonardo e Giovanni Battista.

La cappella del Santissimo Sacramento ha una decorazione tipicamente ottocentesca e accoglie le copie delle due facce di un dipinto di scuola del Ghirlandaio con le Storie di San Romolo e San Romolo fra i suoi compagni, conservato nella cripta.