Po pokoju w Caltabellotcie (1302), kiedy Fryderyk II zawarł ugodę z Andegawenami, Roger musiał poszukać sobie nowego chlebodawcy. Odświeżając kontakty zdobyte podczas rejsów na wschód Morza Śródziemnego, nawiązał negocjacje z Andronikiem II. Cena usług Rogera była dość wygórowana - oprócz sowitego żołdu awanturnik zażądał ręki cesarskiej siostrzenicy, szesnastoletniej Marii Asen, córki ex-cara Bułgarii Iwana Asena III oraz godności megaduksa (μεγας δoυξ). Jeśli jednak zważyć, że Roger cieszył się na Sycylii rangą wiceadmirała i należał do najbliższego otoczenia Fryderyka II, jego apetyty nie wydają się tak nieprzyzwoicie wielkie. W każdym razie desperacko poszukujący substytutu dla własnej tchórzliwej i niewiernej armii Andronik zaakceptował warunki Rogera bez targów. Pozytywna odpowiedź basileusa poniesiona przez posłów na Sycylię uruchomiła proces formowania Kompanii Katalońskiej. Wokół charyzmatycznego Rogera, autora śmiałego planu eskapady na bajecznie bogaty Wschód, skupili się weterani obu stron świeżo zakończonego konfliktu o Sycylię. Przeważali naturalnie wśród nich Katalończycy, co znalazło odbicie w nazwie utworzonej przez Rogera siły zbrojnej. W sierpniu 1303 r.