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