Родился 26 июля 1909 года в Екатеринодаре (Краснодар).

В Красной Армии с 1931. В 1932 году стал членом ВКП(б). Службу начал в 222-м стрелковом полку Красной Армии. Через год был направлен в Ейскую школу морских летчиков, которую окончил в 1934 году. Был оставлен в ней в качестве инструктора-пилота. С 1937 года служил в 12 отдельной авиаэскадрильи КБФ младшим летчиком, а затем командиром звена.

В период с 1939 по 1940 принимал участие в советско-финской войне.  Сражаясь в составе 13-й отдельной истребительной авиационной эскадрильи, в воздушных боях уничтожил один самолёт противника. Совершил более 100 боевых вылетов. 70 раз участвовал в штурмовках по живой силе и технике противника. В одном из боев он сбил самолет Глостер "Гладиатор". За отличное выполнение боевых заданий командования в 1940 году награжден Орденом Ленина.

В начале войны летал на истребителе И-15.  Участвовал в  обороне Одессы.

30 октября 1941 года, при выполнении очередного особо важного разведывательного полёта, Стефан Войтенко был тяжело ранен и отправлен в Севастополь для лечения. После выздоровления - новые воздушные бои, в которых постепенно вырабатывалось, оттачивалось мастерство воздушного бойца. По возвращении в строй, Стефан Войтенко продолжил службу в составе 6-го Гвардейского истребительного авиаполка.

18 апреля 1944 года гвардии капитан С. Е. Войтенко сбил над морем, недалеко от Севастополя, летающую лодку "Гамбург-138", ставшую его 11-й воздушной победой.

К июню 1944 года помощник командира 6-го ГвИАП ( 11-я Гвардейская штурмовая авиационная дивизия ) Гвардии майор С. Е. Войтенко совершил 241 боевой вылет, провёл 45 воздушных боев и лично сбил 12 самолётов противника. Штурмовыми ударами он уничтожил 1 танк, 20 автомашин, 2 зенитные батареи и много другой техники врага. А всего за войну его счет составил 15 самолётов сбитых лично и 21 вместе с боевыми товарищами.

Указом Президиума Верховного Совета СССР от 5 ноября 1944 года за мужество и героизм, проявленные в воздушных боях с немецко-фашистскими захватчиками в небе Кубани и Крыма гвардии майору Стефану Ефимовичу Войтенко присвоено звание Героя Советского Союза с вручением ордена Ленина и медали "Золотая Звезда" (no. 3800)

В отставке с 1947 года.

Скончался 21 апреля 1992 года. Похоронен в Сочи, на Адлерском кладбище.

по материалам Sites.google.com/site/pilotsbaltic