Se desconoce la fecha exacta de su nacimiento. Las hipótesis al respecto se basan se basan en tres datos: 1) Paolo dice que oyó el relato de la batalla de Flovio (el duque Lupo contra los ávaros el a. 664) de boca de excombatientes que entonces eran ancianos.<ref>"Sicut nobis retulerunt (seniores) viri qui in ipso bello fuerunt" Paulus Diaconus, ''Historia langobardorum'', lib. 5, n. 19.</ref> 2) Varios datos indican que Paolo, que formaba parte de la corte de Ratchis, lo siguió a Pavía, cuando este que era duque de Friuli, se convirtió en rey de los longobardos el 744 y se transladótrasladó a la capital. 3) En un poema titulado "Sensi cuius" escrito entre 781-787 con ocasión del anuncio de la boda (que luego no se realizó) de Rotrude, hija de Carlomagno, con Constantino Porfirogénito, hijo de la emperatriz Irene de Constantinopla, Paolo dice de sí mismo: "cetera fugerunt, iam gravante senio" = "el resto se me escapa (i.e. no lo recuerdo), oprimido ya por la vejez". Ya que de niño debió oír el relato de la batalla de Flovio, en edad madura trasladarse con la corte, y ser ya anciano en la década de los 80, por lo tanto debió nacer en torno al 710.
Tampoco se conoce con certeza el lugar de su nacimiento, pero es seguro que fue en la región de [[Friuli]], [[Italia]], en el seno de una familia noble lombarda.
Recibió una educación excepcional, quizá en la corte del rey lombardo en [[Pavía]]. Probablemente fue secretario del rey [[Desiderio]].
