Василий Александрович Стеценко происходит из дворян Курской губернии. В 1830 году зачислен в кадетом в морскую роту Александровского корпуса. В 1833 году переведен в Морской кадетский корпус. В 1837 году произведен в чин гардемарина. В 1839 году окончил Морской кадетский корпус с производством в чин мичмана и оставлен при Офицерском классе. В 1842 году он был назначен на службу на Черноморский флот.
В 1854 году за военные отличия он был произведён в капитан-лейтенанты и назначен адъютантом к князю А. С. Меншикову. В том же году он был послан князем А. С. Меншиковым для наблюдения за высадкой неприятеля, причём на него и его казаков были направлены первые, в Крыму, выстрелы английской пехоты . Появление отряда Стеценко вызвало переполох в лагере англичан, они решили что отряд намерен захватить в плен, находящегося там, английского генерал-квартирмейстера. Этот эпизод описан в английских и французских источниках. В 1855 году состоял начальником артиллерии 1-го отделения оборонительной линии Севастопольской крепости. В том же году Василий Александрович состоя адъютантом при генерал-адмирале, был командирован в Очаков для наблюдения за союзным флотом, блокировавшим крепость Кинбурн, обложенную с сухого пути пути неприятельскими войсками . Пройдя сквозь неприятельский флот Стеценко доставил к Государю Императору сведения о состоянии крепости, за что и удостоился лично получить из рук Императора орден Святого Великомученика и Победоносца Георгия 4-й степени «…за то, что совершил отличный подвиг в ночь с 4 на 5 октября 1855 г., когда с явной опасностью проехал сквозь неприятельскую эскадру, в осажденную англо-французскими войсками Кинбурнскую крепость и, возвратясь из оной, доставил верные сведения о состоянии крепости и гарнизона». В следующем году командирован к наместнику Кавказа и главному командиру Черноморского флота для согласования действий по занятию новых укреплений на северо-восточном берегу Чёрного моря при содействии армии и флота.
В 1858 году Василий Александрович был пожалован флигель-адъютантом к Его императорскому Величеству и назначен командиром корвета «Вол», а затем командиром фрегата «Полкан», 2-го флотского экипажа и 84-пушечного винтового корабля «Выборг». В 1859 году за отличие произведен в чин капитана 1 ранга. В 1861-1862 годах он командовал 9-м флотским экипажем и 135-пушечным кораблём «Цесаревич». В 1863 году по Высочайшему повелению он был командирован в Либаву для предупреждения высадки польских инсургентов на Курляндский берег, имея под своей командой два клипера и шхуну; при этом ему было поручено оказывать содействие сухопутным войскам . В том же году, в виду обострённых отношений у нас с Англией, послан с фрегатом «Генерал-Адмирал» в Темзу для приведения оттуда первого нашего броненосца батареи «Первенец» в каком бы состоянии готовности она не находилась, и за отличное исполнение этого награждён орденом Св. Владимира 3-й степени. 28 октября 1866 года произведён в чин контр-адмирала с оставлением в Свите Его императорского Величества. В 1868-74 годах, командовал отрядом судов броненосной эскадры в звании младшего флагмана. В то же время с Высочайшего соизволения состоял членом разных комитетов. В 1871 году для расчёта казны за подводную лодку, ему было поручено произвести опыты, выдержит ли она давление на глубине 14 сажень (около 30 метров). Через два года Василий Александрович был командирован в Англию для собрания сведений о перевозки войск морем и об их десантных транспортах. 7 января 1874 года произведён в чин вице-адмирала и сопровождал императора Александра II в Англии. Через три года, по тогдашним военным обстоятельствам, назначен начальником обороны Финляндских шхер. В 1883 году назначен членом Адмиралтейств-совета. 1 января 1893 года произведён в чин адмирала. С 1893 года постоянно назначался председателем экзаменационных комиссий для производства гардемарин в офицеры.
Был также членом конференции Николаевской морской академии и Императорского географического общества . Несмотря на парусное воспитание, адмирал Стеценко до конца жизни интересовался за морской наукой и его можно было видеть на всех докладах, лекциях и торжествах по морскому делу.