Tarih boyunca seyyahlar onları Kara Çerkesler, Dağlı Çerkesler, Alanlar, Basiyanlar, Karaçioliler gibi değişik adlarla haritalarına kaydetmişler, onlar kendilerini Tavlu (Dağlı) adıyla anarlarken Kafkas Dağları üzerinde yaşadıkları vadilere göre Karaçaylılar, Bashanlılar, Çegemliler, Holamlılar, Bızıngılılar, Malkarlılar olarak çeşitli zümrelere bölünmüşlerdir. Sovyet hâkimiyetinden sonra bu halk Karaçaylılar ve Balkarlar (Malkarlılar) ya da Karaçay-Balkar (Karaçay-Malkar) halkı olarak literatüre girmiştir.
Karaçay-Malkarlılar atasözlerine kendi dillerinde “Nart söz” adını verirler. “Nartlar” Kafkas halklarının mitolojilerinde, Kafkasyalıların ataları olduklarına inanılan efsanevi bir halktır. Abhaz, Adige, Oset, Çeçen, Dağıstanlı gibi halklarla birlikte Karaçay-Malkar folklorunda da Nart efsaneleri geniş bir yer tutar. Başlıca kahramanları Örüzmek, Sosurka, Batırez, Kara Şavay, Alavgan, Fuk, Satanay Biyçe gibi adlar taşıyan Nart halkının, günümüzdeki Kafkasya halklarının ataları olduğuna dair inanç Kafkas halkları arasında oldukça yaygındır. Karaçay-Malkarlılar bu sebeple çok eski devirlerden beri atasözlerine “Nart söz” adını vermektedirler.
Karaçay etnoniminin kaynağı ise, Karaçay halkının XV. Yüzyılda yaşadığına inandığı Ḳarça isimli ilk beylerinin adına dayanmaktadır ve Karça’nın halkı ~ Karça’nın yurdu anlamlarını taşımaktadır.