Фамилия Андрухненко — один из самых показательных примеров украинской модели на -енко, которая в XVII–XVIII веках стала господствующей в Поднепровье и Слобожанщине. Суффикс -енко в ту эпоху выполнял роль указателя на кровное родство: он означал «сын» или «маленький», так что Андрухненко — это буквально «сын Андруха». Сама основа Андрух — уменьшительно-ласкательная форма имени Андрей, возникшая в живой разговорной речи через характерное для украинского языка чередование: Андрей превращался в Андрух (по той же модели, что Михайло → Михей или Григорий → Гриць). Усечение корня и добавление -ух- давало целое гнездо прозвищных форм: Андрух, Андрушко, Андрущенко.

Существует и вторая, менее вероятная версия происхождения. В некоторых говорах «андрух» или «андруха» — диалектное название черта, лешего или нечистой силы (исследователи выводят его из польского dla drwienia — «для насмешки»). Однако ономасты, в частности Б. Унбегаун в «Русских фамилиях», отмечают, что прозвища с отрицательным значением редко становились основой для фамилий на -енко в крестьянской и казачьей среде, где ценили именно родство по отцу. Поэтому версия с «нечистой силой» выглядит натянутой: Андрухненко — это почти наверняка патроним, а не прозвище.

Географически фамилия плотнее всего сидит в центральной и восточной Украине — Полтавщина, Черкащина, Харьковщина, а также в приграничных областях России (Курская и Белгородская), куда украинские переселенцы принесли свой говор и фамильные модели. В документах XVIII века встречаются однокоренные варианты: Андрущенко, Андрухов, Андрухович. Все они восходят к тому же корню, но различаются суффиксами, которые указывали на социальный статус: -ович — для шляхты и мещан, -енко — для казаков и крестьян. В реестрах Запорожской Сечи патронимы на -енко были нормой — казаков записывали по имени отца, а не по деду или профессии. Так что предок-носитель фамилии, скорее всего, был либо казаком, либо свободным крестьянином, а его отца звали Андрухом, то есть Андреем.