Фамилия Калитенко — типичный пример украинской фамилии, образованной по модели «прозвище + патронимический суффикс -енко». Суффикс -енко в украинской ономастике означает «сын» или «потомок», то есть Калитенко — это буквально «сын Калиты». Такие фамилии массово закреплялись в левобережной и степной Украине в XVI–XVII веках, а затем распространились на юг России и Кубань.

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

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

Фамилия Калитенко встречается в основном на востоке Украины (Сумская, Полтавская, Харьковская области) и в прилегающих областях России — Курской, Белгородской, Ростовской. Это говорит о том, что фамилия закрепилась в зоне расселения украинских казаков и крестьян, которые активно переселялись на южные и юго-восточные земли в XVIII–XIX веках.