Figlio del cerusico Dono di Paolo e della nobildonna Antonia di Giovanni del Beccuto, Paolo si impratichisce dal 1407 al 1414 presso la bottega fiorentina di Lorenzo Ghiberti, dove conosce Donatello e apprende il gusto per il dettaglio naturalistico. Coetaneo di Masaccio e Beato Angelico, il soprannome "Uccello" gli deriva dalla comprovata abilità a dipingere piccoli animali, in particolare uccelli. Nel 1414 si iscrive alla Compagnia di San Luca e nel 1415 all’Arte dei Medici e Speziali. Le prime opere tradiscono uno stile tardo gotico tradizionale. Esegue una Annunciazione e quattro Profeti per la cappella di Paolo Carnesecchi in Santa Maria Maggiore, un Sant'Antonio abate tra i santi Cosma e Damiano per lo Spedale di Lelmo e una Madonna col Bambino per una delle case della famiglia materna. Tra il 1425 e il 1430 è a Venezia, dove oltre a fare la conoscenza delle opere di Pisanello e Gentile da Fabriano in Palazzo Ducale lavora in prima persona ai perduti mosaici per la facciata della Basilica di San Marco. Nel 1430 è forse a Roma con Masolino, con il quale qualcuno ipotizza una collaborazione per il ciclo degli Uomini illustri in Palazzo Orsini. Nel 1431 ritorna a Firenze e si applica alle Storie della Genesi nel Chiostro Verde di Santa Maria Novella, dipingendo prima il riquadro con La creazione degli animali e di Adamo e La creazione di Eva e il peccato originale e poi quello con Il diluvio e la recessione delle acque e Il sacrificio e l’ebbrezza di Noè (1447 - 1448). Tra gli anni ’30 e ’40 del Quattrocento la sua attività si fa più incisiva. Realizza la pala per la chiesa di San Bartolomeo a Quarate, di cui purtroppo resta solo la predella con le tre scene della Visione di San Giovanni a Patmos, dell’Adorazione dei Magi e dei Santi Giacomo Maggiore e Ansano, poi, nel 1435, affresca la Cappella dell’Assunta nel Duomo di Prato con le Storie della Vergine (Natività di Maria e Presentazione di Maria al Tempio), le Storie di Santo Stefano (Disputa di Santo Stefano e Martirio di Santo Stefano) e altre figure di santi. Nel 1436 è di nuovo a Firenze, dove firma l’affresco monocromo con la statua equestre del condottiero Giovanni Acuto (John Hawkwood) in Santa Maria del Fiore. A Bologna realizza nel 1437 l’affresco con la Natività nella chiesa di San Martino. Tra il 1438 e il 1440, o forse più tardi, celebra la recente vittoria dei fiorentini sui senesi in tre dipinti raffiguranti diversi episodi della Battaglia di San Romano, avvenuta nel 1432. Esposti in una sala di Palazzo Medici fino al 1784, i dipinti si trovano ora in tre distinti musei: Niccolò da Tolentino alla testa dei fiorentini (National Gallery, Londra); Disarcionamento di Bernardino della Ciarda (Uffizi, Firenze); Intervento decisivo a fianco dei fiorentini di Michele Attendolo (Louvre, Parigi). Sempre a Firenze, tra il 1443 e il 1445, esegue il quadrante dell’orologio della controfacciata del Duomo e i cartoni con la Resurrezione e la Natività per due vetrate della cupola. Nel chiostro di San Miniato dipinge invece, tra il 1447 e il 1454, gli affreschi con Storie dei santi eremiti. Nel 1445 Donatello lo invita a Padova, dove Paolo realizza gli affreschi con i Giganti per Palazzo Vitaliani. Nel 1452 sposa Tommasa Malifici, che gli darà due figli. In questi anni realizza la famosa tavola con San Giorgio e il drago (1455), oggi alla National Gallery di Londra. Dieci anni più tardi eseguirà una tavola con lo stesso soggetto per Lorenzo di Matteo Morelli. Su invito di Federico da Montefeltro si trasferisce a Urbino dal 1465 al 1468, dove esegue la decorazione di Palazzo Ducale e dipinge la predella con il Miracolo dell'Ostia profanata, su commissione della Compagnia del Corpus Domini.