Paula s-a născut într-o familie creștină, cu stare materială bună, din orașul Nicomidia, Asia Mică, la sfârșitul secolului al III–lea. Părinții i-au oferit tot ce își dorea, au trimis-o la școală și au educat-o să fie bună, blândă și harnică. Asia Mică, actualul teritoriu al Turciei, pe vremea aceea era o adevărată patrie a martirilor pentru credință. Creștinii erau vânați și dați pe mâna autorităților care îi torturau pentru a-i face să renunțe la credința lor. De aceea se vedeau obligați să se roage în catacombe, la marginea orașelor și în cimitirele abandonate.
În comunitatea creștină din Nicomidia, tinerele fete erau instruite să ofere sprijin și alinare celor care erau prinși și închiși dintre creștini. Astfel, încă de mică, Paula a început să prindă drag de Hristos, de Biserică și de ajutorarea aproapelui. Odată ajunsă la vârsta căsniciei, gândul ei era acela de a rămâne fecioară și a I se dedica lui Hristos.
Tânără și firavă, își petrecea o mare parte a timpului prin închisorile din oraș. Lanțuri, sânge, bătăi și schingiuiri, nimic nu o mai impresiona pe Paula: „Îşi păzea fecioria şi se sârguia să se afle vrednică de cămara cerească” după cum ne arată sinaxarul ei.
După moartea părinților, tânăra a moștenit întreaga avere. Atunci singurul ei gând a fost acela că avea să poată ajuta creștinii din temnițe mult mai mult. Folosea averea sa pentru a mitui străjerii, iar aceștia îi facilitau accesul în temniţă, la Sfinţi. Celor chinuiţi de foame şi de sete le aducea hrană şi băutură, celor dezbrăcaţi le dădea îmbrăcăminte, trupurile cele rănite ale mucenicilor le vindeca, iar în timp ce îi îngijea vorbea cu ei despre Dumnezeu și se întărea în credința ei.
La un moment dat, în temnița din Nicomidia a fost adus pentru anchetă Luchilian, un bătrân creștin înțelept, care a fost toată viața închinător la idoli, și care, după l-a descoperit pe Hristos, a propovăduit Evanghelia peste tot pe unde mergea. Alături de el au mai fost aduși și patru tineri: Claudie, Ipatie, Pavel şi Dionisie. Tânăra Paula i-a îngrijit și s-a bucurat de învățăturile lor până când acestia au fost executați. Pe urmă, a adunat corpurile lor și le-a îngropat creștinește.
Deși în oraș era cunoscută ca fiind creștină, Paulei nimeni nu-i făcuse rău, până când a fost denunțată că a îngropat trupurile martirilor. Așa că a fost arestată și închisă în temniță pentru a fi judecată și ea. I s-a propus să se lepede de credința ei dar a refuzat. Mai întâi au aruncat-o în cuptor, iar văzând că iese nevătămată de acolo, i-au tăiat capul cu sabia.
