Первоначально они выполняли здесь свою традиционную роль наемников, аналогичную той, которую сыграли в Арабской империи халифата Аббасидов тремя веками раньше. Первые наемники пришли из колонии туркмен, обосновавшихся в Добрудже, на западном побережье Черного моря, после восхождения на императорский трон первого из Палеологов, Михаила VIII, бежавшего от латинской оккупации и жившего в качестве изгнанника при дворе сельджуков. Эти туркмены пришли на помощь свергнутому с трона султану сельджуков Изз-ед-Дину, который, в свою очередь, нашел убежище в Константинополе. После угрожающей демонстрации против императора они добились освобождения султана из-под стражи и вместе с ним отправились в Крым. Но его сын и отряд его стражи остались в Константинополе, приняли христианство и составили костяк корпуса турецкой милиции, вскоре быстро разросшегося и обеспечившего желанное подкрепление императорской армии.
В начале XIV века византийский император Андроник II аналогичным образом призвал на помощь крупное войско наемников-христиан из Каталонской дружины под командованием не признававшего никаких законов солдата удачи Роже де Флора. Когда каталонцы вызвали в Константинополе беспорядки, он переправил их в Малую Азию. Здесь они успешно сражались против турок, но забирали себе всю военную добычу за счет греков, с которыми они в конце концов вступили в открытый конфликт, основав в Галлиполи европейскую штаб-квартиру и стремясь превратить ее в собственное государство. Когда Роже де Флор был опрометчиво убит в императорском дворце, каталонцы в ярости обрушились на греков и призвали своих прежних врагов — турок из Малой Азии — помочь им в борьбе против империи, которую они пришли защищать.
Таким образом, именно каталонцы были, в первую очередь, ответственны за появление турок в Европе, пригласив их сражаться против греков в качестве организованной силы. Когда каталонцы наконец ушли в Фессалию, они оставили позади себя, во Фракии и Македонии, большое войско турок, совершавших нападения на пути сообщения и сеявших общий беспорядок. Их лидер Халил договорился о выводе войска, в обмен на охранную грамоту для переправы через Босфор. Но когда греки в нарушение договоренности попытались лишить турок их трофеев, Халил вызвал подкрепление из Азии, разгромил греков и вынудил спасаться бегством юного императора Михаила IX, с презрительной насмешкой приняв головной убор императора. Император смог избавиться от турок, только призвав на помощь войска сербов.
Начиная с этого времени на протяжении всего XIV века острова и побережья европейской части Византии подвергались череде пиратских набегов турок из различных княжеств Малой Азии. Только вражда между ними предотвращала согласованное вторжение в то время, когда число турок, сражавшихся на стороне греков, примерно равнялось числу турок, сражавшихся против них. Среди них были татары с северных берегов Черного моря — люди с такими же расовыми корнями и культурными традициями, волнами набегавшие через юг России в Крым и дальше на запад, вплоть до Венгрии. Тем временем турецкие пираты из княжества Айдын в Малой Азии грабили население островов в Эгейском море, спровоцировав Крестовый поход папских войск, захвативших город Смирну.
Собственно османы не принимали в этих враждебных действиях никакого участия, проницательно рассчитав, что тем самым они только ослабят своих враждующих турецких соседей и соплеменников. Хотя к 1330 году османы фактически оккупировали берега Босфора, прямо напротив Константинополя, они оставались верны своей терпеливой, бдительной политике и не пересекали его воды в сторону Европы еще на протяжении семи лет.
Они сделали это по приглашению великого канцлера и узур патора Иоанна Кантакузина, способного и амбициозного лидера, провозгласившего себя императором в противовес законному наследнику, бывшему еще ребенком, Иоанну Палеологу. Кантакузин попросил турок поддержать его в последовавшей за этим гражданской войне. Теперь в обмен на военную помощь Кантакузин, который уже и раньше зондировал для этого почву, предложил в жены Орхану свою дочь Феодору. Предложение было немедленно принято. В 1345 году около шести тысяч османских воинов переправились в Европу. Здесь они помогли узурпатору отбить у Иоанна Палеолога прибрежные города Черного моря, опустошить Фракию, пригрозить Адрианополю (теперь Эдирне) и осадить Константинополь.
В следующем году свадьба византийской принцессы и султана османов была отпразднована на европейских берегах с соответствующей помпой и церемониями. Орхан, разбивший лагерь напротив, в Скутари, направил флот из тридцати турецких судов и эскорт кавалерии, чтобы увезти свою невесту из величественно украшенного коврами павильона, воздвигнутого в лагере императора в Селимбрии. Здесь, как пишет об этом «бесчестье пурпура» Гиббон, «Феодора взошла на трон, закрытый занавесками из шелка и золота; войска выстроились в боевом порядке, но один император был верхом на коне. По данному сигналу занавески мгновенно раздвинулись, и глазам зрителей предстала невеста или жертва, окруженная стоявшими на коленях евнухами и свадебными факелами; звуки флейт и барабанов возвестили о радостном событии, а мнимое счастье новобрачной сделалось темой для песнопений, написанных лучшими поэтами, какие были в то время. Феодора была отдана во власть своего варварского повелителя без соблюдения церковных обрядов, но было условлено, что, живя в Бурсе, в тамошнем гареме, она сохранит свою религию, а ее отец восхвалял смирение и благочестие, которые она выказала в этом затруднительном положении».