Benozzo nacque a Firenze, probabilmente tra il 1420 e il 1421, in una casa in via del Fiore, nel quartiere di Santo Spirito, vicino al Convento del Carmine, la cui grande chiesa fu decorata nel 1427 per volontà della famiglia Brancacci con un esteso ciclo di affreschi compiuti da Masaccio, opera che rivoluzionò l'arte a Firenze e che certamente ebbe influenza sulla formazione del giovane Benozzo.
Anche la frequentazione del contado a ridosso delle colline fiorentine nella zona di Settimo non dovette essere indifferente all'educazione professionale dell'artista. In questa località, di cui era originaria la famiglia - che qui continuò ad avere proprietà e legami parentali - Benozzo poté sicuramente affinare le capacità di osservazione che avrebbero distinto tutta la sua produzione artistica, come ebbe già modo di notare Giorgio Vasari nelle Vite de' più eccellenti architetti, pittori, et scultori italiani (1568) definendolo pittore "di grandissima invenzione e molto copioso negli animali, nelle prospettive, ne' paesi e negli ornamenti".
Benozzo fu avviato dal padre presso una bottega di pittura per compiere il proprio tirocinio; ciò avvenne probabilmente non prima del 1435, se si ipotizza che abbia frequentato prima la 'scuola primaria' (corrispondente alle nostra scuola elementare) e successivamente la cosiddetta 'scuola dell'abaco', dove si approfondivano le conoscenze nella scrittura e si acquisivano competenze amministrative, utili a chi perseguiva la professione di mercante o artigiano in proprio. Non ci sono documenti che attestino questa formazione scolastica del pittore, ma è una congettura degli studiosi basata, in primo luogo, sulla prassi del tempo, secondo la quale i figli di artigiani sufficientemente benestanti erano indirizzati a questo genere di studi e, in seconda istanza, dal grado di familiarità del Gozzoli con la scrittura, attestata dai documenti autografi e dalle molte iscrizioni che si leggono nei suoi dipinti, con i caratteri all''antica' e con il corretto uso della lingua latina.

L'ipotesi sostenuta dal Vasari, che Benozzo fosse stato discepolo di Beato Angelico, non è concordemente accettata dalla critica anche per l'impossibilità da parte dell'Angelico, che fu in primo luogo un frate domenicano, di tenere all'interno di un convento una bottega di pittura vera e propria, frequentata anche da apprendisti laici. Non è, inoltre, ancora assodato il fatto che Benozzo abbia potuto frequentare la bottega di Zanobi Strozzi, il più valido miniatore a fianco dell'Angelico, che potrebbe invece aver conosciuto più tardi durante la sua collaborazione alla decorazione del convento di San Marco.
In questo periodo vi erano molte botteghe a Firenze, per lo più dislocate nell'attuale via dei Calzaiuoli, nelle strade adiacenti e nella zona dietro al Duomo. Nell'impossibilità di conoscere con certezza la bottega presso la quale svolse il proprio tirocinio, è stato ipotizzato che dapprima Benozzo abbia frequentato un artista non distante dalla propria abitazione, forse Bicci di Lorenzo, maestro dipintore a capo di una delle botteghe più attive a Firenze e iscritto insieme al figlio Neri, pittore coetaneo del nostro, alla confraternita di Sant'Agnese con sede nel Convento del Carmine.
Certo è che nell'ottobre del 1439 Benozzo partecipò alla realizzazione della preziosa coltre funebre (il drappo usato durante la cerimonia per l'esposizione solenne del feretro) commissionata proprio da questa confraternita. Dai documenti dell'epoca Benozzo risulta, infatti, come "dipintore" anche se non possiamo sapere con certezza se fosse già un maestro autonomo iscritto alle arti.
La sua formazione e il suo stile personale sono testimoniati fin dalle prime opere realizzate in autonomia, come la Madonna col Bambino e angeli della National Gallery di Londra, decorata con preziose stoffe broccate che rivelano una delle qualità specifiche di Benozzo, ovvero quella sua abitudine di curare minuziosamente i tessuti preziosi rendendoli quasi reali. È assai probabile che tale abilità nel distinguere e rappresentare le diverse stoffe fosse derivata dal padre che, praticando l'attività di farsettaio (cioè di sarto), lo aveva certamente educato fin da piccolo in questa tradizione, offrendogli l'opportunità di osservare ed ammirare da vicino i manufatti tessili.

E' ormai certa la sua partecipazione alla decorazione a fresco del convento di San Marco, un cantiere esteso ed impegnativo condotto magistralmente da Beato Angelico, tra 1439-1440 e il 1443-1444, nel quale la critica è sempre più concorde nell'ipotizzare un rapporto di collaborazione più che di discepolato.
Conclusi i lavori a San Marco, Benozzo s'impegnò a collaborare con Lorenzo Ghiberti alla seconda porta del Battistero, la cosiddetta porta del Paradiso. Il contratto tra i due artisti è datato al 1° marzo 1444 e la paga corrisposta a Benozzo fu consistente già dal primo anno, andando ad aumentare nei due successivi (la collaborazione doveva infatti concludersi nel 1447). Durante questo incarico Benozzo ebbe modo di affinare le capacità relative alla raffigurazione prospettica. Sulla base di concordanze stilistiche con i suoi dipinti, a lui sono attribuite alcune scene della Porta del Paradiso, specialmente nelle due ultime formelle con le Storie di Saul e David e con l'Incontro della regina di Saba e di re Salomone.