Willehaldo era originario de Nortumbría, en Inglaterra. Probablemente se educó en York, pues fue amigo de Alcuino. Después de su ordenación, las conquistas espirituales que muchos de sus paisanos habían hecho para Cristo (como san Willibrordo en Frisia y san Bonifacio en Alemania), le encendieron en deseos de ir a predicar al verdadero Dios en alguna de esas naciones bárbaras. Hacia el año 766, desembarcó en Frisia y empezó a predicar en Dokkum, cerea del sitio en que san Bonifacio y sus compañeros habían recibido la corona del martirio el año 754. Después de bautizar a algunos conversos, el santo se internó hacia la región de Overyssep, sin dejar de predicar por el camino. En Humsterland, Willehaldo y sus compañeros estuvieron a punto de perecer, ya que los habitantes echaron suertes para decidir si debían exterminarlos. Pero Dios dispuso que la suerte los favoreciese. En vista de ese incidente, san Willehaldo juzgó más prudente volver a Drenthe y trabajar en los alrededores de Utrecht, cuyos habitantes eran menos hostiles. A pesar de la obra llevada Cabo por san Willibrordo y sus sucesores, quedaban todavía muchos paganos por convertir. Desgraciadamente, el celo indiscreto de algunos misioneros hizo más mal que bien. En efecto, ciertos compañeros de Willehaldo demolieron los templos de los paganos, quienes se enfurecieron tanto, que decidieron darles muerte. Uno de ellos descargó con tal fuerza su espada sobre el cuello del santo, que su cabeza habría ido a dar muy lejos, a no ser porque el acero pegó contra un grueso cordón del que llevaba siempre colgado un relicario, lo que le salvó la vida, según dice su biógrafo. Aunque debe notarse que este incidente se parece sospechosamente al que se cuenta de san Willibrordo en la isla de Walcheren.
Habiendo tenido tan poco éxito entre los frisios, san Willehaldo se trasladó a la corte de Carlomagno, quien el año 780, le envió a evangelizar a los sajones, a los que acababa de someter. El santo se dirigió a los alrededores de la actual Bremen y fue el primer misionero que cruzó el Weser. Algunos de sus compañeros llegaron hasta más allá del Elba. Durante algún tiempo, todo iba perfecamente, pero el año 782, los sajones se rebelaron contra los francos y mataron a todos los misioneros que cayeron en sus manos. San Wilehaldo huyó por mar a Frisia. Poco después, aprovechó una oportunidad para trasladarse a Roma a informar al papa Adriano I acerca del estado de su misión. Después pasó dos años en el monasterio de Echternach, que san Willibrordo había fundado. Allí reunió a sus compañeros de misión, a los que la guerra había dispersado, e hizo una copia de las Epístolas de San Pablo.
Carlomagno ahogó en sangre la rebelión de los sajones. Willehaldo regresó entonces a la región que se extiende entre el Weser y el Elba, donde fundó numerosas iglesias. El año 787, Carlomagno le nombró obispo de los sajones. El Santo fijó su residencia en Bremen. Según parece, dicha ciudad se fundó por aquélla época. El celo de san Willehaldo en la predicación era ilimitado. El 19 de noviembre de 789 consagró su catedral, construida de madera, en honor de San Pedro. Algunos días más tarde, cayó gravemente enfermo. Uno de sus discípulos le dijo llorando: «No abandonéis vuestro rebaño a la furia de los lobos». Pero él respondió: «¿Cómo podéis impedirme que vaya a Dios? Dejo a mis ovejas en manos de Aquél que me las confió, cuya misericordia es capaz de protegerlas». Su sucesor le sepultó en la nueva iglesia de piedra construida en Bremen. San Willehaldo fue el último de los grandes misioneros ingleses del siglo VIII.
Casi todos los datos que poseemos sobre san Willehaldo provienen de una biografía latina escrita hacia el año 856 por un clérigo de Bremen. Antiguamente, se atribuía esa biografía a san Anscario; actualmente se ha abandonado esa teoría, aunque parece que san Anscario escribió la relación de los milagros que acompaña a la biografía. El mejor texto de ambos documentos es el que publicó A. de Poncelet en Acta Saactorum, nov., vol. III, editado anteriormente por Mabillon y por Pertz, Monumenta Germaniae Historica, Scriptores, vol. II. Véase también a H. Timerding, Die christliche Frühzeit Deutschlands, vol. II (1929) ; Louis Halphen, Etudes critiques sur l'histoire de Charlemagne (1921) ; y Hauck, Kirchengeschichte Deutschlands, vol. II. Cf. W. Levison, England and the Continent (1949).