He was the third-born son of Malatesta da Verucchio (Dante's "Mastin Vecchio") and his first wife Concordia dei Pandolfini.

The wedding was a diplomatic success by Malatesta da Verucchio who aspired to possess the territories of the Ghiaggiolo family.

[3] They had two children: Uberto II, who bore the noble title, and Margherita, future bride of Aghinolfo Guidi di Romena.

[4] The union was not happy, however, as the young man's feelings were for his sister-in-law Francesca da Polenta, wife of his brother Giovanni, who had aroused keen interest in him since their first meeting when she thought she had to marry Paolo and not Gianciotto.

[5] Traditionally Paolo has been portrayed as a romantic, beautiful figure, not very inclined to aspirations for power, instead focused on culture and the pleasures of life.

His diplomatic skills led him to be chosen by Pope Martin IV as Captain of the People in Florence in March 1282.