奥斯曼人国家的诞生笼罩着传奇的迷雾，不过对于这个日后让整个基督教欧洲为之颤抖的大帝国，传说故事似乎恰能反映出它在起源上的某些特质。
传说，一位名叫奥斯曼(Osman)的年轻战士与当地伊斯兰教长谢赫?艾德巴利(Sheikh Edebali)的女儿玛尔赫顿（Malkhatun）坠入爱河。但奥斯曼家实在太穷了，根本无法迎娶他的心上人，唯一的希望只有在沙场上奋力拼搏赢得荣誉。在一次战斗中，奥斯曼俘虏了赫蒙西克要塞(Khirmencik)的主人，希腊人克泽?米哈伊尔(Kose Mikhal)，并与之结为好友。这天，奥斯曼作了一个奇怪的梦，他隐隐感到这是上天的预兆，又惊又喜，便找谢赫?艾德巴利倾诉，他说，在梦里一轮明月(象征着玛尔赫顿)从谢赫的胸膛升起，同时奥斯曼的胸膛上长出了一棵极伟岸的大树(古代突厥人的图腾)，树冠直插入云霄，与明月遥相辉映，而树根连通着四条大河(底格里斯河Tigris、幼发拉底河Euphrates、尼罗河Nile和多瑙河Danube)，突然一阵狂风吹起，大树上那一片片剑一般的叶子齐刷刷的指向君士坦丁堡城(Constantinople)……奥斯曼觉得，这个梦似乎说明他和心上人必定终成眷属，谢赫却兴奋的告诉他，事情远没这么简单，上天启示他必将统治世界！就这样，奥斯曼毫无阻碍的娶到了谢赫的女儿，他以及他子孙的征服事业也随之开始了。
在另一则关于奥斯曼人起源的传说中，他们的祖先是一位叫苏莱曼?沙赫(Suleyman sah)的人，他是土库曼（即‘突厥人’）卡依(Kayi)部落的领袖，在12世纪晚期统治着伊朗东部的马罕地区(Mahan)。13世纪早期，他带着数千土库曼人为躲避蒙古人的铁蹄向西迁移，在横渡幼发拉底河的时候，苏莱曼不幸落水淹死，部众随之分裂。他的两个儿子率领大部分人重回呼罗珊(Khorasan)，为蒙古效力；另一个叫埃尔托格鲁尔(Ertugrul)儿子则带着剩余的卡依部落成员到达塞尔柱人(Seljuk)统治下的安纳托利亚(Anatolian)。做为罗姆苏丹国(Sultanate of Rum)的附庸，埃尔托格鲁尔得到了一块位于安纳托利亚西部边陲的土地，以及两小块位于弗里吉亚(Phryga)的土地，一块叫瑟于特(Sogut)，一块叫多马尼奇(Domanic)。当埃尔托格鲁尔去世之际，他把这一地区统治权和卡依部落的领导权一起交给了他的儿子奥斯曼。
这些传说有很多版本，但根据史料推断，进入安纳托利亚的奥斯曼人的祖先并不是13世纪躲避蒙古人而来，而是早在11世纪曼齐克特之战(Battle of Manzikert)后扩散到小亚细亚的。在长达两个世纪里。他们是无根的游牧人。而奥斯曼本人很可能与埃尔托格鲁尔并无血缘，但的确是个占据拜占庭边境省份的土库曼加齐(gazi，意为圣战者，信仰战士)和穆斯林农民的头目，并且和当地城市的阿赫(ahi，穆斯林中类似于行会和兄弟会的社会组织)有很深的联系，谢赫?艾德巴利也许就是阿赫的领袖。
借助同盟的力量，奥斯曼趁着塞尔柱人崩溃之际占据了卡拉贾希萨要塞(Karacahisar)，建立起自己的小政权。此时蒙古人西征的风头正劲，很多穆斯林战士和宗教学者领袖避难来到小亚，而失去拜占庭军事支援的基督教边境领主，比如克泽?米哈伊尔，也纷纷转而为奥斯曼效力。同时，基督徒农民苦于拜占庭帝国的苛捐杂税和土地贵族的欺凌压迫，早已对现状不满，也是奥斯曼可以利用的力量。
13世纪最后十年奥斯曼贝伊(Bey，地方官员的头衔)的小王国已拥有8座边境要塞，以及在十字军时期以多里留姆之战(Battle of Dorylaeum)闻名的土耳其城市伊兹谢希尔(Eskisehir，意为旧城，多里留姆是拉丁名)。1299年奥斯曼占领了他王国中第一个有意义的城市耶尼谢希尔(Yenisehir，即新城)，该城成为奥斯曼第一个真正意义上的首都。不过迄今为止，奥斯曼和他的继承人所占据的疆域还只是一条狭长地带，不发达的边境省。很多大城市还在拜占庭人的掌握之中，在乡村小城镇的居民看来，奥斯曼人也不过是随着季节变换走出山岭，迁徙、放牧和骚扰的游牧部落，因此奥斯曼若想进一步发展，首要任务是将他的人民转化为定居者。1301年，奥斯曼在科雍希萨尔(Koyunhisar)击败了拜占庭人的军队，从而声名远播，越来越多的加齐加入奥斯曼的队伍。随着奥斯曼埃米尔国在耶尼谢希尔的建立，奥斯曼致力于两个方向的扩张，一是从萨卡里亚河(Sakarya)向北扩张到黑海；二是向西南占据马尔马拉海(Marmara)沿岸肥沃的土地。到1308年，他达到了目标，从而孤立了拜占庭在本地区最后一个重要城市布尔萨(Bursa)。依靠着海上援助，布尔萨顽强抵抗多年，但最终在1326年陷落。对于奥斯曼人，占领布尔萨意义重大。他们的王国从一个游牧的边境国家转变为一个有首都，边界和定居居民的真正的国家，一个加齐帝国——真主信仰的执行者和传播者，安拉神圣的宝剑——不断战争，不断扩张，以战利品和土地为饵料茁壮成长的巨人。

奥斯曼人征服的基本国策是由奥斯曼本人制定的，在发展壮大过程中，奥斯曼既是率领土库曼加齐反对异教徒的埃米尔，他还是恢复安纳托利亚的社会秩序和政治统一的阿赫协会领袖。这项国策由奥斯曼的继承人传承下来，当西土耳其别的加齐埃米尔国纷纷衰落之际，唯独奥斯曼人取得了成功。也许是拜占庭、巴尔干等国的顽抗使他的军队和政府越发坚强，使饱受战略的移民纷纷聚集于此，稳扎稳打，步步为营。通过不断蚕食拜占庭的边界，奥斯曼人获得了比其他土库曼埃米尔有利得多的生存空间，并将拜占庭压缩至君士坦丁堡周围微不足道的一隅，只有黑海南岸的特拉布松(Trabzon)还在希腊人手中。在某些时候，奥斯曼土耳其明智的作为拜占庭的同盟和保护人出现，使其免遭竞争对手，比如其他土库曼人、鞑靼人和拉丁人的征服。