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

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

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