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 Wilibrordo En Frieslandia y San Bonifacio en Alemania), le encendieron en deseos de ir a predicar alverdadero Dios en alguna de esas naciones bárbaras. Hacia el año 766, desembarcó en Frieslandia 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. (El Martirologio Romano afirma, erróneamente, que Willehaldo fue discípulo de San Bonifacio). 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 Wilibrordo 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. Este incidente se parece sospechosamente al que se cuenta de San Wilibrordo 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 Frieslandia. 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 Wilibrordo había fundado. Ahí 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". É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.