Родился 26 июля 1909 года в Екатеринодаре ( Краснодар ), в семье рабочего. Окончил неполную среднюю школу, затем работал трактористом. В рядах Красной Армии с 1931 года. Окончил Ейскую школу морских лётчиков в 1934 году и работал в ней инструктором.

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

На фронтах Великой Отечественной войны с июня 1941 года. Был заместителем командира эскадрильи 8-го истребительного авиаполка ( ВВС Черноморского флота ), участвовал в героической обороне Одессы.

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

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

А всего за войну его счет составил 15 самолётов сбитых лично и 21 вместе с боевыми друзьями.

5 ноября 1944 года, за успешные бои в небе Кубани и Крыма отважный лётчик был удостоен звания Героя Советского Союза.

После войны Стефан Ефимович остался на службе в ВВС. С 1947 года - в запасе. Живя в Сочи, вёл большую военно - патриотическую работу, часто выступал перед школьниками и на предприятях. Ветеран рассказывал о своих боевых друзьях, а в историко - краеведческом музее был активным экскурсоводом.

За время службы награжден Орденами Ленина ( дважды ), Красного Знамени ( дважды ), Отечественной войны 1-й степени, Красной Звезды, медалями.