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

Региональный след фамилии указывает на её исконно русское происхождение. Куленины встречаются в документах XVII–XVIII веков на территории бывшего Белгородского уезда и в южных уездах Рязанской губернии. Это говорит о том, что носители фамилии были, скорее всего, служилыми людьми «по прибору» (стрельцами, пушкарями, казаками) или крестьянами, которые получили фамилию от своего мирского прозвища. В отличие от многих фамилий на -ов/-ев, которые часто носили бояре и дворяне, фамилии на -ин были типичны для посадского и сельского населения.

Спорный момент: в некоторых говорах слово «куленя» могло означать не имя, а прозвище по внешности или поведению — например, «кудрявый» или «вялый, сонный» (от диалектного «куля» — мешок, куль). Однако эта версия слабее, так как не подкреплена устойчивой традицией прозвищ в документах. Правдоподобнее всего, что Куленин — это «сын Николки», где Николка через чередование (Николай → Микулай → Куля → Куленя) дал фамилию, которая звучит не как отчество от полного имени, а как прозвище, закрепившееся в роду.