Фамилия Улексин — редкий случай, когда основа читается неочевидно. На первый взгляд в ней слышится что-то греческое или церковное, но на самом деле перед нами типичная русская фамилия, образованная от имени или прозвища через суффикс -ин. Суффикс указывает на принадлежность: «чей?» — Улексин, то есть сын или потомок человека по имени или прозвищу Улекса.

Главная загадка — что такое Улекса. Скорее всего, это просторечная, обиходная форма канонического имени Алексей. В русской народной традиции имена часто укорачивали и переделывали до неузнаваемости: Алексей превращался в Алексу, Лексу, а с добавлением начального гласного «у» (по аналогии с Ульян из Юлиан) мог возникнуть вариант Улекса. Такая модель встречается в фамилиях Ульянов, Устинов, где «У-» появилось из начального «Ю-» или «И-». Если эта версия верна, то предок носителя фамилии Улексин — человек по имени Алексей, которого в быту звали Улексой.

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

Фамилия крайне редкая. Она не фиксируется в крупных справочниках по русским фамилиям (например, у Унбегауна или Никонова), что говорит о её локальном бытовании. Скорее всего, Улексины — потомки одного рода из конкретной губернии, где имя Улекса было в ходу. Сословно предки могли быть крестьянами или мещанами: фамилии на -ин в этой среде преобладали.