Один из шести 60-пушечных фрегатов типа «Тенедос», построенных в Николаеве под наблюдением адмирала А. С. Грейга. По размерам и вооружению они не слишком уступали 74-пушечным линейным кораблям и иногда именовались 60-пушечными кораблями[1]. Назван в память о взятии русской армией при активной поддержке Черноморского флота 29 сентября 1828 года турецкой крепости Варна.
Фрегат «Варна» был заложен в Николаеве и после спуска на воду в 1832 году вошел в состав Черноморского Флота.
В 1833 году принимал участие в экспедиции Черноморского флота на Босфор[2]. 2 февраля в вышел из Севастополя составе эскадры контр-адмирала М. П. Лазарева и к 8 февраля прибыл в Буюк-Дере. 28 июня, приняв на борт войска, с эскадрой вышел из Буюк-Дере и, высадив войска в Феодосии 3 июля, к 22 июля вернулся в Севастополь.
В 1838 году принимал участие в Абхазской экспедиции. Вместе с корветом «Мессемврия» прикрывал строительство форта Александрия[3]. В ночь с 30 на 31 мая 1838 года во время стоянки на рейде в устье реки Сочи корабли попали в сильный шторм и были выброшены на берег[4]. Спасшиеся члены экипажей подверглись нападению убыхов[5], но были отбиты русскими войсками. Останки же кораблей разграблены и сожжены горцами. В результате кораблекрушения и нападения горцев погибли более 30 человек из экипажей кораблей[3].