Варна была сильной крепостью с гарнизоном в 12 тысяч человек. Попытки четырехтысячного отряда начать осадные работы с суши 1 июля были отражены обороняющимися. Но 21 июля эскадра Грейга доставила в Каварну десятитысячный отряд вице-адмирала A. C. Меншикова; эти войска на следующий день осадили Варну.
Получив 15 июля извещение о желании Императора побывать на флоте и затем направиться в Одессу, Грейг подготовил отряд судов и предложил принять монарха в Каварне. Но на следующий день вблизи города появились турецкие войска. Чтобы обеспечить его оборону, адмирал высадил егерский полк и батарейную роту. 21 июля прибыло повеление Грейгу возглавить осаду Варны, а Меншикову командовать сухопутными войсками.
Немедленно были высажены на берег оставшиеся войска, которые по суше двинулись к Варне. 22 июля к крепости подошел и флот. В тот же день флагман послал капитана 2-го ранга Мелихова для осмотра и снятия плана крепости. На следующий день он сам с группой генералов и адмиралов на пароходе «Метеор» прошел вдоль укреплений. Турки огня не открывали.
24 июля 1828 года вместе с группой сановников Николай I посетил «Париж» и после осмотра корабля высказал Грейгу благодарность за отличное устройство флота и покорение Анапы. Отбывая в Одессу на фрегате «Флора», Император приказал истребить флотилию под крепостью.
Утром 25 июля адмирал послал Ботьянова в Варну с предложением о сдаче. Одновременно корабли приблизились к крепости, как бы поддерживая ультиматум. Но уже через час турецкий чиновник доставил отказ коменданта, который рассчитывал на победу. И основания у капудан-паши Иззет-Магомета были. Первоклассная крепость располагала сильным гарнизоном; многочисленные войска вне крепости были готовы оказать поддержку.
Получив отказ, Грейг приступил к решительным действиям. 26 июля 22 русских гребных судна истребили 14 турецких, прикрывавших крепость с моря, что позволило русским кораблям с 26 июля по 29 сентября обстреливать крепость. Командовал операцией капитан 2-го ранга Мелихов. Были собраны по два гребных судна от каждого корабля и фрегата. К 20.00 они собрались у бригантины «Елизавета», которую поставили на полпути от флота к крепости. В 23.00 отряд отправился, был обнаружен и обстрелян. Тем не менее в ночной схватке русские моряки взяли 14 судов и 2 вооруженных баркаса, 46 пленных, лишившись всего 4 человек убитыми и 37 ранеными. За это лихое дело Император выразил Мелихову монаршую признательность и пожаловал следующим чином.
Постепенно наладилась и блокада с суши. Если двухтысячный отряд в начале кампании мог только наблюдать за крепостью, то доставленные Грейгом 10 тысяч войск обложили крепость с западной и северной сторон. Для связи с осадными войсками адмирал высадил 350 моряков, которые построили у берега редут, куда была перевезена часть провианта, пристань и телеграф. Еще 500 человек были отправлены для постройки осадных батарей под командованием капитана 2-го ранга Залесского. Одновременно начался обстрел с моря: обычно беспокоящую пальбу вел корабль или фрегат, а при необходимости стрельбу вели 2 корабля и 2–3 бомбардирских судна. В частности, 26 июля фрегат «Святой Евстафий» успешно обстрелял турецкий отряд, пытавшийся обойти левый русский фланг.
Чтобы пресечь снабжение крепости по Лиману, 3 августа по просьбе Меншикова туда был отправлен баркас, который начал боевые действия в тот же день.
Продолжалось крейсерство судов. 5 августа фрегат «Поспешный» привел два судна, взятые у стен Мидии и Инады; третье судно пришлось затопить.
7 августа после совета, состоявшегося накануне, адмирал приступил к атаке всем флотом. Корабли построили линию баталии вслед за транспортом «Редут-Кале», который проводил промеры. Один за другим корабли проходили мимо крепости, поочередно обстреливая ее. Этот маневр, названный «Варнским вальсом», продолжался с 14.00 до 17.00 и привел к разрушениям в Варне без особого ущерба для атакующих. Из-за мелководья корабли стреляли по одному с дистанции пять кабельтовых; тем не менее удалось подавить огонь приморского бастиона.
Видимо, в ответ на обстрел турки 9 августа предприняли крупную вылазку. В бою был ранен Меншиков. Грейг немедленно прибыл на берег с врачом. Николай I, узнав о ранении князя, 15 августа назначил командовать войсками под Варной графа Воронцова и просил адмирала облегчить доставку к Каварне продовольствия для войск, осаждавших Шумлу.
В августе отличился капитан 1-го ранга Н. Д. Критский. Объединив свой крейсирующий отряд, он 17 августа направился к Инаде, где неприятель сосредоточил большие запасы пороха и снарядов. Оставив в охранении шлюп «Диана», он с фрегатами «Поспешный», «Рафаил», катером и бригом обстрелял укрепления и, высадив 370 человек, лично командовал взятием крепости, лишившись всего 6 человек (1 убитый, 5 раненых). Русские успели погрузить пушки с батарей, увести 12 судов из порта, взорвать батареи и уничтожить склады ранее, чем турки прислали подкрепления. За успешное выполнение задачи Критский был награжден орденом Святого Владимира III степени.