Karamanlıların, bazı kaynaklarda Oğuzların Afşar boyundan, bazı kaynaklarda ise Salur boyundan oldukları geçmektedir. Hangi boydan geldikleri ile ilgili tam bir görüş birliği bulunmamaktadır. Afşar boyundan geldikleri ile ilgili görüşler ağırlık kazanmaktadır.[61]
Karamanlıların atalarının XII. yüzyılda Aral Gölü’nün doğusundaki Maveraünnehir bölgesinde yaşadığı ile ilgili bilgiler bulunmaktadır. Moğol baskısı nedeni ile yüzyılın ortalarında anayurtlarını terk etmek zorunda kalan Karamanlılar önce Azerbaycan’a gelip yerleşmişler, daha sonraları ise batıya doğru hareket etmişlerdir. Karaman aşiretinin Anadolu'ya geçen büyük kısmı, I.Alâeddin Keykubad tarafından 1228'de Mut ve Ermenek civarlarına yerleştirilmiştir.[62]
Aşiretin beyi Kerimeddin Karaman’ıın dedesi Oğuz beylerinden Sâdeddin Bey, babası da Nûr-e Sûfî (Nûr Sûfî) diye anılan Nûreddin Bey’dir. Hayatının ilk döneminde Ermenek’te kömürcülük işi ile uğraşan bir bey olan Nur-e Sufi, Baba İlyas’ın Selçuklulara karşı başlattığı isyanlarda onun yanında yer almış, kurduğu tarikatın (Babai Tarikatı) müntesibi olmuştur. Tarikat meseleleri ile uğraştığından aşiretinin yönetimini oğlu Karaman’a bırakmıştır. Kendisine ‘sufi’ denilmesinin nedeni tarikatın sadık bir müridi (halifesi) olmasındandır. Karamanoğulları hâkimiyetlerindeki bölgeye sonradan gelenlerle birlikte çoğalmış, civar yerleşim birimlerine akınlar düzenleyerek sahip oldukları toprakları genişletmişlerdir. Selçuklular, Kösedağ (1243) mağlubiyetinden sonra zayıflamış, eski güçlerini kaybetmişlerdir. Bazı Türkmen aşiretleri bu durumdan vazife çıkarmış, Selçuklu karşısındaki pozisyonlarını değiştirmişlerdir. En belirgin pozisyon değişikliği Karamanoğullarında görülmüştür. Türkiye Selçuklularının Moğollara ikinci kez yenildiği 1256 Sultanhanı-Aksaray savaşı, Karaman Bey’in konumunu güçlendirmesine ve daha bağımsız hareket etmesine neden olmuştur. Sultan IV.Kılıçarslan güçlenen Karamanoğullarının olası bir başkaldırısını önlemek ve güney sınırını güvenlik altına almak amacıyla Karaman Bey’e 1262’de Uç Beyliği unvanı vermek zorunda kalmıştır.[63] İlk yıllarda uç beyliğin merkezi Ermenek (Karaman’ın ilçesi) iken sonraları Larende (Karaman) olmuştur. Karamanlılar, Moğol yenilgisinden sonra eski gücünü kaybeden Türkiye Selçuklularından doğan otorite boşluğunu doldurmaya ve onların yerini almaya yönelik bir siyaset gütmüşlerdir.
Selçuklular ile Karamanoğulları arasındaki ilk çatışma Karaman Bey zamanında olmuştur. Selçukluların Antalya’daki bazı Türkmen boylarını denetim altına alma amacıyla almış olduğu sert tedbirler, sıranın kendilerine de gelebileceğini düşünen Karaman Bey’i harekete geçirmiştir. 20 bin kişilik ordu ile Konya’ya sefer düzenleyen Karaman Bey mağlup olmuş ve geri çekilmek zorunda kalmıştır.