Yeleçli Köyü’nün bilinen en eski adı Samzalek veya Samzelek’tir. Köy adı, 1886 tarihli Rus nüfus tespitinde “Samzalek” (Самзалек), 1928 tarihli Osmanlıca köy listesinde ise “Samzelek” (سامزەلك) olarak kayıtlarda yer almaktadır.
Samzelek Köyü, Orta Çağ’da Gürcistan’ı oluşturan tarihî bölgelerden biri olan Kola bölgesi sınırları içerisinde yer almaktadır. Günümüzde Türkçe’de Göle olarak bilinen bu bölge, 16. yüzyılın ikinci yarısında Osmanlı Devleti tarafından Gürcülerden alınarak Osmanlı hâkimiyetine girmiştir.
1877–1878 Osmanlı-Rus Savaşı (93 Harbi) sonrasında imzalanan Berlin Antlaşması (1878) ile Kola (Göle) bölgesi ve Samzelek Köyü, Osmanlı Devleti tarafından Rusya’ya bırakılmıştır. Rus idaresi döneminde köy, Ardahan Sancağı’na bağlı Göle Kazası sınırları içinde yer almıştır. Bu dönemde köyde ağırlıklı olarak Rum nüfusun yaşadığı, köy nüfusunun 1886 yılında 152 kişi olduğu tespit edilmiştir.
Köy nüfusu, 1896 yılında 240, 1906 yılında ise 298 kişi olarak kayıtlara geçmiştir. Yaklaşık yirmi yıl içinde nüfusun iki katına yakın artması, bu süreçte köye yeni nüfus yerleştirildiğini göstermektedir. Nitekim Gürcü tarihçi ve arkeolog Ekvtime Takaişvili, 1907 yılında yayımlanan çalışmalarında, 1877–1878 Osmanlı-Rus Savaşı sırasında Göle bölgesinde boşalan köylere yeni nüfus iskân edildiğini belirtmiştir.
Birinci Dünya Savaşı’nın ardından Rus birliklerinin bölgeden çekilmesiyle Samzelek Köyü, kısa bir süre fiilen Ermenistan sınırları içinde kalmıştır. Ancak 16 Mart 1921 tarihinde imzalanan Moskova Antlaşması ile köy resmen Türkiye Cumhuriyeti topraklarına dâhil edilmiştir.
Cumhuriyet’in ilk yıllarında Samzelek Köyü, 1928 tarihli Osmanlıca köy listesinde, Kars Vilayeti’nin Göle Kazası’na bağlı Okam Nahiyesi sınırları içerisinde yer almaktadır. 1940 Genel Nüfus Sayımı’nda köy adı “Varginis” biçiminde kaydedilmiş olup, bu dönemde köy nüfusu 337 kişi olarak tespit edilmiştir.
Türkçe kökenli olmayan yer adlarının değiştirilmesi kapsamında, köyün adı 1959 yılında 7267 sayılı Kanun uyarınca “Yeleçli” olarak değiştirilmiştir. 1965 Genel Nüfus Sayımı’nda Yeleçli Köyü’nün nüfusu 672 kişi olarak kaydedilmiş; bu nüfusun 272’sinin okuryazar olduğu tespit edilmiştir.
