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

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

Географически фамилия тяготеет к центральным и восточным областям Украины: Черкасской, Полтавской, Киевской. В России фамилия встречается реже, часто среди потомков переселенцев с Украины. Интересно, что в русском языке существует параллельная форма — Каличкин, образованная от той же основы, но с другим суффиксом, а также фамилия Каликов. Вариант Каличенко, с характерным украинским суффиксом, однозначно указывает на происхождение рода из украинской среды.

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