Paulino também pregou a palavra na província de Lindisfarne, a primeira na margem sul do rio Humber, que se estende até o mar, e o governador da cidade de Lindisfarne, cujo nome era Blaecca, foi o primeiro a se converter ao Senhor com sua família. Nessa cidade, ele também construiu uma igreja de excelente alvenaria; cujo telhado, seja por longo descuido ou pela mão de um inimigo, parece ainda estar de pé, e todos os anos alguns milagres de cura costumam ser mostrados no mesmo lugar para o benefício daqueles que fielmente os buscam. Nessa igreja, Paulino, quando passou para Cristo Justo, consagrou Honório bispo em seu lugar, como diremos a seguir em seu devido lugar.
A respeito da fé desta província, um certo presbítero e abade, um homem veraz do mosteiro de Peartane, chamado Deda, contou-me que um certo ancião lhe relatara ter sido batizado ao meio-dia pelo Bispo Paulino, na presença do Rei Edwin e de uma grande multidão de pessoas, no rio Treenta, perto da cidade que em inglês se chama Tiuulfingacæstir; o mesmo ancião também descrevia a imagem do próprio Paulino como um homem alto, um pouco curvado, de cabelos negros, rosto magro, nariz adunco, de aparência ao mesmo tempo venerável e terrível. Ele também tinha consigo em seu ministério o diácono Tiago, um homem certamente diligente e nobre em Cristo e na Igreja, que permaneceu até os nossos dias.
Mas naquela época, dizia-se que reinava tanta paz na Grã-Bretanha, onde quer que o comando do Rei Edwin chegasse, que, como diz um provérbio até hoje, mesmo que uma mulher com um recém-nascido quisesse atravessar a ilha a pé, de um mar a outro, não conseguiria fazê-lo sem se machucar. O mesmo rei era tão atencioso com o bem-estar de seu povo que, na maioria dos lugares onde via nascentes de água cristalina perto de travessias públicas, ordenava que postes de madeira fossem erguidos para o refresco dos viajantes, e que ninguém, exceto em casos de necessidade, ousava tocá-los por causa de sua grandeza, seja por medo dele ou por amor a ele. Mas ele teve tamanha excelência em seu reinado que não apenas em batalha os estandartes eram carregados à sua frente, mas também em tempos de paz, quando cavalgava entre cidades, vilas ou províncias com seus ministros, o porta-estandarte costumava sempre ir à frente; Também não era costume ele carregar aquele tipo de estandarte, que os romanos chamam de tufa e os ingleses de thuuf, sempre que caminhava pelas ruas.