W 678 Wilfryd stracił swój urząd, gdy arcybiskup Canterbury, Teodor, podzielił jego diecezję na trzy mniejsze. Niezadowolony Wilfryd udał się na skargę do Rzymu. W czasie podróży zboczył z trasy z powodu sztormu i wylądował na wybrzeżu pogańskiej Fryzji. Spędził wśród Fryzów zimę, rozwijając tam akcję misyjną. Dotarłszy do Rzymu uzyskał poparcie papieża Agatona, lecz gdy powrócił w 680 roku do Anglii, został z rozkazu króla Egfryda wtrącony do lochu.
Po wyjściu z więzienia po dziewięciu miesiącach udał się w tułaczkę po Mercji i Wessexie, jednak z obu tych krajów został wypędzony. Ostatecznie dotarł do Sussexu, ostatniego pogańskiego państwa w Brytanii. Spędził tam pięć lat (681–686), przekonał władcę i jego otoczenie do przyjęcia chrztu i założył klasztor w Selsey.
W 685 roku Sussex został podbity przez Caedwallę z Wessexu. Caedwalla, mimo że był poganinem, po podboju Sussexu przekazał Wilfrydowi liczne nadania ziemskie. Ostatecznie Caedwalla przyjął chrzest trzy lata później. Wilfryd tymczasem pogodził się z arcybiskupem Teodorem i ponownie objął biskupstwo Yorku, tym razem już jednak znacznie okrojone. Jednak w 691 roku znów wybuchł spór związany z okrojeniem biskupstwa, zaś Wilfryd ponownie został wygnany i udał się ze skargą do Rzymu.