Родился 22 декабря 1916 года в селе Гришино ныне Молчановского района Томской области в семье крестьянина. Русский.  Его дед Устин Макарович Бокша был полным кавалером Георгиевского креста за участие в Крымской кампании.
Окончил среднюю школу.
В рядах Красной Армии с 1936 года. Участник боев на реке Халхин-Гол в 1939 году. На фронтах Великой Отечественной войны с июля 1941 года. Начинал войну в боях за Москву, участвовал в Курской битве, освобождал Украину, Польшу, закончил войну в Чехословакии. Член ВКП(б)/КПСС с 1943 года.
Несколько раз был ранен.
Старшина роты 1128-го стрелкового полка (336-я стрелковая дивизия, 60-я армия, 1-й Украинский фронт) Денисенко в одном из боев 11–21 марта 1944 года за город Тернополь заменил выбывшего из строя командира взвода, ворвался с бойцами в село Смыковцы, захватил вражеское орудие, лично поразил двух гитлеровцев. 23 апреля 1944 года Денисенко награжден орденом Славы 3-й степени.
При наступлении на населенный пункт Броды (90 км северо-восточнее Львова) 14 июля 1944 года командир отделения Денисенко поднял бойцов в атаку, в ходе которой забросал гранатами пулеметную точку противника, обеспечив продвижение подразделения. В уличном бою сразил свыше десяти гитлеровцев. 27 августа 1944 года награжден орденом Славы 2-й степени.
При форсировании реки Пшемша под населенным пунктом Имилин (16 км юго-восточнее города Катовице, Польша) командир пулеметного расчета Денисенко 24–28 января 1945 года вывел из строя несколько десятков вражеских солдат и офицеров. Участвовал в предъявлении ультиматума командованию окруженной вражеской группировки и в пленении гитлеровцев. Им были захвачены большие трофеи.
23 мая 1945 года Денисенко награжден орденом Славы 1-й степени.
Степан Петрович признан одним из самых лучших снайперовВторой мировой войны – на его счету 181 вражеский солдат. Он участник Парада Победы в Москве в июне 1945 года.
Степан Петрович бросил к подножию мавзолея В.И. Ленина личный штандарт Гитлера.
В 1945 году Денисенко демобилизован. Окончил Ташкентский финансово-экономический институт. Более тридцати лет проработал инженером-экономистом на заводе «Сибтекстильмаш» в Новосибирске.
Награжденорденом Отечественной войны 1-й степени, многими медалями.
Степан Петрович – почетный гражданин городов Золочев и Буск Львовской области. Активно участвовал в жизни города – являлся членом военно-научного общества при окружном Доме офицеров СибВО, Новосибирской секции советского комитета ветеранов войны, Областного комитета ветеранов войн и военной службы; участвовал в военно-патриотическом воспитании подрастающего поколения.
Степан Петрович Денисенко ушел из жизни 25 сентября 2000 года.
В Новосибирске на доме, где жил Степан Петрович по улице Станиславского, 12, установлена мемориальная доска. Его имя увековечено на Аллее Героев у Монумента Славы