Piero il Gottoso, che si occupava della cura e dell'arredo del nuovo palazzo di via Larga, decise di affidare a Benozzo l'incarico di dipingerne la cappella privata, confidando nella straordinaria capacità del pittore di rendere la varietà e la vivacità dei soggetti con un'altrettanta realistica interpretazione dei ritratti, delle vesti e dei paesaggi. Nacquero così, nel 1459, gli affreschi del celeberrimo Corteo dei Magi, in cui alla fastosa processione dei tre re fanno da sfondo straordinari paesaggi ricchi di dettagli dal sapore fiabesco che sembrano dilatare gli angusti spazi della piccola cappella. Nel desiderio dei committenti l'episodio evangelico doveva costituire solo un pretesto per celebrare la potenza e la ricchezza della famiglia dei Medici, ben sottolineata dall'opulenza delle vesti, in un ambiente che aveva sicuramente una duplice valenza di luogo di preghiera e luogo di rappresentanza per piccole udienze private.
Con questo incarico, ancora oggi considerato il capolavoro di Benozzo, si può sancire l'ingresso dell'artista tra i pittori di fiducia della potente famiglia medicea.

Anche se per la natura strettamente privata la piccola cappella rimase preclusa agli occhi di molti contemporanei, Benozzo raggiunse grande fama e ricevette le commissioni per importanti lavori su tavola. Fra questi ci sono pervenuti la Madonna col Bambino e nove angeli (Museo di Detroit), il pilastrino con tre santi entro formelle dorate (Galleria dell'Accademia di Firenze) e la pala d'altare per la Confraternita della Purificazione - che aveva la propria sede in alcuni locali del convento di San Marco. Nel contratto relativo a quest'opera i committenti avevano esplicitamente richiesto al pittore di seguire l'impostazione della pala che l'Angelico aveva dipinto per la chiesa di quel convento. Conservata alla National Gallery di Londra, la pala di Benozzo era arricchita dalle tavolette della predella ora disperse in diversi musei del mondo.
Un'ulteriore commissione per un'opera di prestigio pervenne al pittore dalla ricca famiglia Alessandri: la "racconciatura" del polittico trecentesco di Lippo di Benivieni in San Pier Maggiore, ovvero l'ammodernamento, secondo il gusto dell'epoca, dell'antico dipinto. Di questo lavoro sono sopravissute, di Benozzo, le quattro tavolette della predella con le Storie dei santi raffigurati nella tavola maggiore, conservate al Metropolitan Museum di New York.
Tra le opere realizzate in questo periodo si ricorda, inoltre, la predella conservata al Museo di San Marco che doveva far parte di una pala non ancora identificata.

Probabilmente a causa di una epidemia di peste che nel 1463 colpì la città di Firenze, Benozzo, forte della fama conseguita e forse grazie a una mediazione della famiglia Medici, si trasferì in quell'anno a San Gimignano dove il dotto erudita agostiniano fra' Domenico Strambi gli commissionò un prestigioso ciclo di affreschi con le Storie di Sant'Agostino per la chiesa della città. L'impresa doveva celebrare le gesta del santo e Benozzo vi attese con la consueta maestria, mediante la tecnica dell'affresco, suo medium espressivo prediletto. Questa capacità professionale, che gli valse appunto la fama "di "ottimo maestro in muro", come lo ricordano gli stessi collaboratori che parteciparono a questa impresa, gli portò nuovi incarichi in questa città. Durante il soggiorno a San Gimignano Benozzo inviò in Umbria, al convento dei minori osservanti di Santa Maria dell'Oro presso Terni, il Matrimonio mistico di santa Caterina d'Alessandria - forse parte di uno smembrato polittico per l'altare maggiore della chiesa dedicata alla Vergine -, tuttora conservata presso la pinacoteca della città. Come è stato già detto in merito al secondo soggiorno romano di Benozzo, non fu questa l'unica occasione in cui il pittore inviò ad altre sedi alcune sue opere.

La permanenza a San Gimignano non impedì all'artista di intrattenere rapporti anche con altri committenti del territorio. Così il vicario di Certaldo, che aveva delega di amministrare la giustizia dell'intera Valdelsa anche nelle cause capitali, gli commissionò, nel 1465, il tabernacolo dei Giustiziati, allora collocato presso il ponte sul fiume Agliena. In questo luogo, infatti, i membri della Confraternita della Giustizia si prendevano cura delle ultime ore di coloro che erano stati condannati a morte, confortandoli con le loro preghiere e invitandoli al pentimento.