Согласно турецкой исторической традиции, часть племени кайы откочевала в Анатолию из Средней Азии, где предводители кайы некоторое время находились на службе у правителей Хорезма. Вначале тюрки-кайы избрали местом кочевья земли в районе Караджадага к западу от нынешней Анкары. Затем часть их перебралась в районы Ахлата, Эрзурума и Эрзинджана, доходя до Амасьи и Алеппо (Халеба). Некоторые кочевники племени кайы нашли себе пристанище на плодородных землях в районе Чукурова. Именно из этих мест небольшое подразделение кайы (400–500 шатров) во главе с Эртогрулом, спасаясь от набегов монголов, направилось во владения сельджукского султана Алаэддина Кейкубада I. Эртогрул обратился к нему за покровительством. Султан пожаловал Эртогрулу удж (окраинная область султаната) на землях, захваченных сельджуками у византийцев на границе с Вифинией. Эртогрул принял на себя обязательство защищать границу сельджукского государства на территории дарованного ему уджа.
Удж Эртогрула в районе Мелангии (тур. Караджахи-сар) и Сегюта (к северо-западу от Эскишехира) был невелик. Но правитель был энергичен, а его воины охотно участвовали в набегах на соседние византийские земли. Действия Эртогрула облегчены были немало тем, что население пограничных византийских областей было крайне недовольно грабительской налоговой политикой Константинополя. В результате Эртогрулу удалось несколько увеличить свой удж за счет пограничных областей Византии. Трудно, правда, точно определить масштабы этих захватнических операций, как, впрочем, и первоначальные размеры самого уджа Эртогрула, о жизни и деятельности которого нет сколько-нибудь достоверных данных. Турецкие хронисты, даже ранние (XIV–XV вв.), излагают много легенд, связанных с начальным периодом сложения бейлика Эртогрул. Эти легенды гласят, что жил Эртогрул долго: он умер в возрасте 90 лет в 1281 или, по другой версии, в 1288 г.
Сведения о жизни сына Эртогрула, Османа, давшего имя будущему государству, тоже в немалой мере легендарны. Осман родился примерно в 1258 г. в Сегюте. Этот горный малонаселенный район был удобен кочевникам: здесь было много хороших летних пастбищ, хватало и удобных зимних кочевий. Но, пожалуй, главным преимуществом уджа Эртогрула и наследовавшего ему Османа было соседство с византийскими землями, что давало возможность обогащаться за счет набегов. Эта возможность привлекала в отряды Эртогрула и Османа представителей других тюркских племен, обосновавшихся на территориях других бейликов, так как завоевание принадлежавших немусульманским государствам территорий почиталось у адептов ислама делом священным. В результате, когда во второй половине ХШ в. правители анатолийских бейликов в поисках новых владений воевали между собой, воины Эртогрула и Османа выглядели борцами за веру, разоряя в поисках добычи и с целью территориальных захватов земли византийцев.
После смерти Эртогрула правителем уджа стал Осман. Судя по некоторым источникам, были сторонники передачи власти брату Эртогрула, Дюндару, но тот не рискнул выступить против племянника, ибо видел, что его поддерживает большинство. Через несколько лет потенциальный соперник был убит.
Осман направил свои усилия на завоевание Вифинии. Зоной его территориальных притязаний стали области Брусы (тур. Бурса), Белокомы (Биледжика) и Никомедии (Измита). Одной из первых военных удач Османа стал захват в 1291 г. Мелангии. Этот небольшой византийский городок он сделал своей резиденцией. Поскольку прежнее население Мелангии частью погибло, а частью бежало, надеясь найти спасение от войск Османа, последний заселил свою резиденцию выходцами из бейлика Гермиян и других мест Анатолии. Христианский храм по велению Османа был превращен в мечеть, в которой его имя стало упоминаться в хутбах (пятничных молитвах). Согласно легендам, примерно в это время Осман без особого труда добился от сельджукского султана, власть которого стала совсем призрачной, титула бея, получив соответствующие регалии в виде барабана и бунчука. Вскоре Осман объявил свой удж самостоятельным государством, а себя – независимым владетелем. Произошло это около 1299 г., когда сельджукский султан Алаэддин Кейкубад II бежал из своей столицы, спасаясь от взбунтовавшихся подданных. Правда, став практически независимым от Сельджукского султаната, который номинально существовал до 1307 г., когда последний представитель династии румских Сельджукидов был задушен по приказу монголов, Осман признал верховную власть монгольской династии Хулагуидов и ежегодно посылал в их столицу часть дани, которую собирал с подданных. От этой формы зависимости Османский бейлик освободился при преемнике Османа, его сыне Орхане.