Фамилия Полтенко относится к распространённому на востоке Украины типу семейных именований с суффиксом -енко. Первоначально такие фамилии указывали на отчество: Иваненко — «сын Ивана», а Полтенко, соответственно, — «сын Полтеня». За этим именованием, в свою очередь, стояло прозвище, которое давали предку по роду его занятий или внешнему виду.

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

Какая версия правдоподобнее, сказать сложно: обе укладываются в логику прозвищ, данных по ремеслу. Но вторая выглядит несколько более узкой: слово «полть» в значении «кусок мяса» было широко распространено в южнорусских и украинских говорах, а прозвища по роду занятий в этой среде встречались часто. В то же время связь с «полтянкой» менее очевидна фонетически, хотя и возможна.

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