Paulinus eventually convinced Edwin to convert, baptizing him and many of his followers in 627.
When Edwin was defeated and killed in battle in 633, Paulinus took the queen and her children to Kent, and spent the remainder of his life at Rochester.
Paulinus was a monk at St Andrew's Monastery in Rome, when, in 601, Pope Gregory I sent him to join Mellitus and others in the second group of missionaries to England.
Although Paulinus' deacon, James, remained in the North and struggled to rebuild the Roman mission, it was monks from the rival Celtic tradition who eventually re-established Christianity in the region, York eventually becoming a mere bishopric.
A legend once told in the town of Caistor concerning St. Paulinus of York states that as the saint was riding an ass along the ancient trackway that runs near the town, he met a man sowing corn.