Герой Советского Союза.
Командир роты 17-го гвардейского стрелкового полка 5-й гвардейской стрелковой дивизии 11-й гвардейской армии 3-го Белорусского фронта, гвардии старший лейтенант.
Родился 7 октября 1922 года в селе Танюшевка Новопсковского района Луганской области в крестьянской семье. Украинец. Член КПСС с 1945 года. Окончил среднюю школу.
В октябре 1941 года призван в ряды Красной Армии. Окончил курсы младших лейтенантов. В боях Великой Отечественной войны с августа 1942 года. Воевал на 3-м Белорусском фронте.
В ночь на 25 апреля 1945 года командир роты 17-го гвардейского стрелкового полка гвардии старший лейтенант С.Я. Нехаенко умело организовал форсирование пролива, соединяющего Балтийское море с заливом Фришес-Хафф, ныне Калининградский залив. Рота захватила плацдарм на побережье косы Фрише-Нерунг, ныне Балтийская, удержав захваченный рубеж до подхода подкрепления.
Указом Президиума Верховного Совета СССР от 29 июня 1945 года за образцовое выполнение боевых заданий командования и проявленные при этом мужество и героизм гвардии старшему лейтенанту Степану Яковлевичу Нехаенко присвоено звание Героя Советского Союза с вручением ордена Ленина и медали "Золотая Звезда" (№ 7653).
После окончания Великой Отечественной войны продолжил службу в армии. Окончил Военную академию имени М.В. Фрунзе. Работал райвоенкомом в Киеве. С 1973 года полковник С.Я. Нехаенко — в запасе. Жил в Киеве. Скончался 25 февраля 1996 года.
Награжден орденом Ленина, орденом Отечественной войны 1-й степени, двумя орденами Красной Звезды, медалями.