Фамилия Лутаенко — характерный пример восточноукраинской модели образования фамилий с помощью суффикса -енко. Этот суффикс, один из самых распространённых в украинской ономастике, изначально указывал на родство по отцу: «чей?» — «Лутаенко» означает буквально «сын Лутая» или «потомок Лутая». Со временем семейное прозвище закрепилось за родом и потеряло прямую связь с отцовством, став наследственной фамилией.

В основе фамилии лежит прозвище Лутай. Его корень восходит к украинскому диалектному слову «лут» — так называли лыко, мочало, то есть лубяные волокна липы. Из этого сырья на Руси и в Украине делали рогожи, циновки, лапти, верёвки и кули. Человек, который занимался заготовкой или обработкой лыка, мог получить прозвище Лутай — по ремеслу. Это типичное «профессиональное» именование, каких много в крестьянской среде: оно указывало на занятие предка, а не на его личные качества.

Интересно, что украинское «лут» родственно древнерусскому лѫтъ — «лыко». В некоторых говорах слово сохранилось и в форме «лут» (ср. белорусское «лут» — «лыко»). Таким образом, прозвище Лутай могло бытовать в разных регионах, где был развит промысел по добыче лыка — в лесной и лесостепной полосе Украины, на Полесье, в приграничных областях России. Фамилия Лутаенко встречается сегодня прежде всего на востоке Украины, в Сумской, Полтавской и Харьковской областях, а также в прилегающих районах России.

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

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