10 января 1834 г. юноша окончил Морской кадетский корпус четвертым в своем выпуске по успеваемости и сразу же был принят в Офицерский класс при корпусе и этот класс 10 марта 1837 г. окончил первым, с занесением фамилии на мраморную доску и производством в лейтенанты. Начальство корпуса сочло нужным оставить молодого человека для педагогической деятельности.
С 23 августа 1837 г. Феодосий Фёдорович начал преподавать в гардемаринских классах астрономию и навигацию, с октября был назначен помощником инспектора классов. С 1 февраля 1838 г. преподавал аналитическую геометрию в Офицерском классе, а с 27 августа 1846 г. являлся заведующим Офицерским классом. В этот период им были составлены два учебных пособия для гардемарин: «Начальные основания динамики и гидростатики» (1842 г.), «Начальная геометрия». 8 июня 1855 г. на заседании Физико-математического отделения Академии наук академики П.Л. Чебышев и В.Я. Буняковский дали благоприятный отзыв курсу «Начальной геометрии»: «Труд во многих отношениях самостоятельный, который своими неотъемлемыми достоинствами обратил полное наше внимание уже при самом появлении его в свет в 1853 г. <…> Нет сомнения, что хорошее руководство по предмету одной из основных наук математики, приспособленное к нуждам флотского офицера, должно считаться у нас весьма важною заслугою; в этом отношении вполне добросовестный труд г. Веселаго достоин всякой похвалы». Критических замечаний со стороны академиков не было, книгу признали классической и ходатайствовали о награде орденом Св. Владимира.
С 1846 по 1853 г. молодой лейтенант заведовал Офицерским классом, одновременно налаживая работу типографии Морского корпуса на коммерческих началах. Ему приходилось ему выполнять много обязанностей – вплоть до корректора. В это период в типографии стали печатать необходимые новые пособия для преподавания корабельной архитектуры, морской артиллерии, физики, механики, книги для изучения иностранных языков, навигационные таблицы.
И это при том, что все летние кампании Ф.Ф. Веселаго он проводил в плавании со своими подопечными. Доводилось ему ходить и на знаменитых впоследствии фрегатах «Паллада» и «Аврора».
В этот период Веселаго проявил себя не только как способный преподаватель, но и талантливый педагог. С 29 апреля 1847 г. приказом начальника Главного Морского штаба за десятилетнюю при Корпусе службу лейтенант Веселаго стал получать двойной оклад.