La majeure partie de la musique de Paolo a été publiée dans des éditions modernes dans les années 1970, ce qui l'a rendue facilement accessible et a attiré l'attention des critiques plus que d'habitude. Sa musique présente des aspects progressistes et conservateurs. La plupart de ses œuvres musicales qui subsistent sont profanes et sont toutes des œuvres vocales, mais deux compositions sacrées (un Benedicamus Domino pour deux voix et un Gaudeamus omnes in Domino pour trois voix) ont aussi survécu. Il est impossible de savoir combien d'œuvres sacrées et profanes de Paolo ont été perdues, mais comme l'intérêt pour la musique profane a explosé au XIVe siècle, la proportion des œuvres profanes aux œuvres sacrées de Paolo qui ont subsisté peut bien correspondre à la répartition réelle de l'ensemble de ses œuvres entre ces deux catégories.
Ses compositions profanes sont de trois types : il y a 13 madrigaux, 46 ballate (certaines sont fragmentaires, et l'attribution d'autres à Paolo a été effacée dans la source) et 5 chansons profanes diverses. Sa musique est toute pour deux ou trois voix et datable d'avant 1410 d'après les sources ou les caractéristiques du style. On ne sait pas si Paolo a composé après 1410.
Ce qui intrigue le plus en ce qui concerne la musique de Paolo, c'est que 32 pages du Codex Squarcialupi, recueil que Paolo a probablement supervisé, portent toutes le nom du compositeur dans la marge supérieure, débutent par un portrait de lui et ne contiennent rien d'autre que des portées vides. On a supposé que sa musique n'était pas disponible à la date limite d'assemblage du codex, mais les pages vierges n'ont pas été retirées. Hoppin pense que Paolo se trouvait en fait à l'extérieur de Florence, au service du cardinal Acciaiuoli, lorsqu'on assembla ce manuscrit, ce qui explique peut-être l'absence de sa musique.
Les madrigaux de Paolo combinent la notation française et italienne et montrent une influence considérable de l'école maniériste avignonnaise de l'ars subtilior par leurs motifs rythmiques complexes et intriqués, mais la plupart ne sont que pour deux voix, ce qui est un choix conservateur. Les ballate sont plus progressistes dans l'ensemble ; la plupart, pour trois voix, sont lyriques, mélodiques, mais présentent encore la complexité mélodique extrême de l'école de l'ars subtilior. L'influence de Landini, difficile à éviter pour tout compositeur florentin de la fin du XIVe siècle, est évidente tant dans les madrigaux que dans les ballate.
