Фамилия Леюшкин образована от имени или прозвища Леюшка. В основе, скорее всего, лежит уменьшительная форма от крестильного имени Леонид (через народное Леон) или от редкого имени Лев. Суффикс -юш- в русских именах (Ванюша, Кирюша, Лелюша) придаёт ласкательный, домашний оттенок. Таким образом, Леюшка — это «маленький Леон» или «Левушка», которого в быту называли чуть иначе.

Менее вероятная, но возможная версия связывает фамилию с диалектным словом «леюха» — так в некоторых говорах называли ленивого, нерасторопного человека. Однако для прозвищ с суффиксом -юш- такое значение нетипично: обычно этот суффикс закреплён за личными именами, а не за нарицательной лексикой.

Фамилия встречается в основном в центральных и северных областях России, особенно в бывших владениях Новгорода и Вологды. Там фамилии на -ин, образованные от имён на -а/-я, особенно часты. Леюшкин — типичный пример такой модели: от основы на -я (Леюшка) прибавили притяжательный суффикс -ин, что буквально означает «сын Леюшки».

В дореволюционных переписях Леюшкины записаны в основном как крестьяне и мещане. Дворянских родов с такой фамилией не обнаружено, что подтверждает её простонародное происхождение. Однокоренные фамилии — Леонов, Леонтьев, Левшин — более распространены, но Леюшкин сохранил именно ту форму, которая передаёт непосредственное, семейное прозвище предка.