Кременчуцький ліцей з посиленою військово-фізичною підготовкою почав свою історію зі створення у Кременчуці в 1999 році на базі Центру допризовної підготовки ліцейного класу з посиленою військово-фізичною підготовкою. В цей рік було здійснено перший набір вихованців, який складався з 30-ти юнаків.
У 2000 році розпочав свою роботу Полтавський обласний ліцей з посиленою військово-фізичною підготовкою. Чисельний склад ліцеїстів становив 80 чоловік.
У 2003 році за значні досягнення у підготовці майбутніх офіцерів, вагому роботу з військово-патріотичного виховання, активну участь у громадському житті міста управлінням освіти і науки облдержадміністрації було вручено особовому складу Прапор ліцею.
У 2005 році Полтавський обласний ліцей з посиленою військово-фізичною підготовкою перейменовано у Кременчуцький ліцей з посиленою військово-фізичною підготовкою Полтавської обласної ради.
Навчальний процес із загальноосвітніх дисциплін організовується на базі Кременчуцького педагогічного коледжу ім. А.С.Макаренка.
Ліцеїсти є неодноразовими переможцями районних олімпіад, призерами обласних предметних олімпіад з базових дисциплін , успішно захищаються на конкурсі творчих науково-дослідних робіт Малої академії наук. Щорічно випускники вступають до вищих військових навчальних закладів , вищих навчальних закладів МВС, МНС.
Ліцеїсти є постійними учасниками міських та районних урочистих заходів.