Sposò a Roma il 18 giugno 1396Gherardo Appiano, signore di Piombino: negli otto anni del loro matrimonio ebbero tre figli, un maschio e due femmine, e, alla sua morte, assunse la reggenza in nome del primogenito Jacopo, di circa cinque anni. Caterina diventerà la seconda signora di Piombino e Violante, nata dopo il decesso del genitore, sarà la moglie di Rodolfo Angiolo da Camerino.[4]
Paola Colonna, risoluta e volitiva, pretese di continuare ad amministrare la signoria anche dopo il raggiungimento della maggiore età da parte del figlio. In seguito alla scomparsa di Jacopo II, privo di prole, il governo sarebbe dovuto spettare al cognato Emanuele Appiano, unico fratello vivente di Gherardo, ma Donna Paola decise di succedere lei stessa, contro le disposizioni testamentarie del marito sulla legge salica. Fu un provvedimento significativo per Piombino che avrà in futuro sei sovrane regnanti. La famiglia Appiano dimorava nell'omonimo palazzo (ancora esistente, seppure modificato e con diversa destinazione): dal 1465 al 1470 l'architetto Andrea Guardi, per volere di Jacopo III, realizzerà la nuova residenza destinata ad accogliere una corterinascimentale più prestigiosa che richiamerà artisti quali il Sodoma e Rosso Fiorentino.[5]
Nel 1442 la signora stipulò un ulteriore accordo di accomandigia, questa volta con la repubblica di Siena che confermò il dominio degli Appiano sulle isole d'Elba (economicamente fondamentale per le sue risorse minerarie), Montecristo e Pianosa. Fece costruire nuove strade e riprendere la costruzione delle mura di cinta. Dal punto di vista diplomatico, inoltre, inviò un ambasciatore a Tunisi per trattare la pace con il bey che aveva intenzione di assediare Piombino. Nel 1444 raggiunse personalmente Siena per partecipare all'ufficiatura in onore del religioso predicatore Bernardino, deceduto qualche mese prima a L'Aquila.[6]
Morì all'età di 65 anni, il 30 novembre 1445, e fu sepolta, accanto al consorte, nella cripta degli Appiano del duomo di Piombino. Escluso per la seconda volta il fratello di Gherardo, Emanuele, le subentrò la figlia Caterina, sposatasi con un suo lontano parente, il nobile romano Rinaldo Orsini, del ramo di Tagliacozzo: questi, comandante di una compagnia di ventura, aveva i mezzi per difendere la famiglia regnante e la signoria.[7]
