Poważne bunty wybuchły w Palermo, gdzie rebeliantów wspomógł papież Hadrian IV, który odmówił Wilhelmowi uznania jego koronacji z roku 1151, obawiając się uzależnienia od rosnącego w siłę królestwa Normanów. Buntownicy opanowali większą część królestwa, a okazję wykorzystali zewnętrzni wrogowie – przeciwko Wilhelmowi wystąpili wspólnie niemiecki władca Fryderyk I Barbarossa, który wnet zdobył koronę cesarską (czerwiec 1155) i cesarz bizantyński Manuel I Komnen, którego wojska zajęły w 1155 Bari, Trani i Tarent, następnie obległy Brindisi, zajmując tereny, które podlegały Bizancjum, dopóki nie przejęli ich Normanowie.
Mimo niepowodzeń Wilhelm zawarł sojusze z włoskimi republikami Genui i Wenecji, co skłoniło Fryderyka Barbarossę do wycofania wojsk, a w 1156 w bitwie pod Brindisi Wilhelm pokonał armię i flotę Bizantyńczyków, zmuszając ich do opuszczenia Italii. Wilhelm na powrót opanował zbuntowane miasta, zachowując przy życiu ich mieszkańców, jednak najbardziej buntownicze Bari zostało ukarane całkowitym praktycznie zburzeniem (1156), ostały się jedynie niektóre kościoły, w tym bazylika św. Mikołaja. W tej sytuacji w 1156 w Benewencie papież Hadrian IV zawarł z Wilhelmem konkordat, uznając jego królewską władzę oraz prawo do powoływania biskupów w całej południowej Italii, w zamian Wilhelm został papieskim lennikiem.