Феодосий Фёдорович Веселаго родился в 27 марта (8 апреля) 1817 года в Роченсальме (фин. Ruotsinsalmi). Его отец был морским офицером. В возрасте десяти лет (1827 год) был принят в Морской кадетский корпус, а в 1837 году, по окончании курса, был прикомандирован к Морскому корпусу, произведен в лейтенанты, в том же году начал преподавать астрономию и навигацию в гардемаринских классах и назначен исправляющим должность помощника инспектора классов. С 1838 года начал читать в офицерских классах аналитическую геометрию, а в 1846 году назначен заведующим этими классами. Плавал с гардемаринами по Финскому заливу и Балтийскому морю. В 1853 году был произведён в майоры с зачислением по армии и назначен инспектором студентов Московского университета. С 1857 по 1860 год в звании полковника назначен на должность помощника попечителя Казанского учебного округа. В 1860 году, с чином коллежского советника, поступил в Петербургский цензурный комитет. С 1860 года под его руководством велись работы по составлению истории русского флота. С 1873 года он был назначен главой комиссии по разбору, описанию и изданию дел архива Морского министерства до 1805 года. С 1862 года — действительный статский советник; с 28 октября 1866 по 22 июня 1881 года — член Совета Главного управления по делам печати; занимал должность начальника Главного управления, с 14 декабря 1869 года — член Комитета морских учебных заведений. С 1872 года — тайный советник. С 22 июня 1881 года стал директором гидрографического департамента Морского министерства и председателем учёного отделения Морского технического комитета и Комитета морских учебных заведений, а в 1892 году — генералом Корпуса флотских штурманов. Был членом правления Императорского российского общества спасания на водах. Похоронен в Санкт-Петербурге на Новодевичьем кладбище.