Фамилия Безненко звучит на украинский лад, и это первая подсказка. Суффикс -енко — один из самых распространённых в Украине, он образует фамилии от личных имён, прозвищ или названий профессий и буквально означает «маленький», «сын» или «потомок» того, кто назван в корне. То есть Безненко — это «сын Безны» или «потомок человека по прозвищу Безна».

Корень фамилии — «безн-». Самое очевидное, что приходит на ум, — слово «бездна». В старину «бездна» означала не только пропасть, но и что-то огромное, неисчислимое, а также могла быть прозвищем человека безрассудного, отчаянного или, наоборот, очень глубокого, скрытного. Однако есть и более бытовая версия: в южнорусских и украинских говорах «безна» могла быть диалектным вариантом слова «бедняк» (от «без» и «иметь» — без имущества). Человека, у которого ничего нет, могли прозвать Безной — иронично или с сожалением.

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

Встречается фамилия в основном в центральных и восточных областях Украины, а также в прилегающих регионах России. Поскольку суффикс -енко типичен для казацкой среды, предки Безненко могли быть казаками или крестьянами, получившими фамилию по прозвищу. В документах XIX века такая фамилия нередко фиксировалась в Харьковской и Полтавской губерниях.