Осаду Анапы пришлось вести на два фронта — со стороны крепости делали вылазки турки, а с тыла наседали на русский отряд огромные толпы черкесов. На первое время, благодаря неопытности солдат десанта, не имевших еще дела с горцами, солдаты платились жизнью при малейшей оплошности. Так, 12 мая 20 застрельщиков 13-го егерского полка, преследуя горцев, слишком далеко удалились от своего батальона — и немедленно были окружены горцами и изрублены все до одного. Казаки же, наоборот, сами умели завлекать горцев в невыгодные для них стычки. На первых же порах при таких стычках у черкесов пали два видных предводителя — владетельный князь Ханаш-Ибин-Цако и князь Темрюк. Ранним утром 26 мая убежавший из плена, после 8 лет неволи, солдат известил, что в ближайших горах скрывалось от 2 до 3 тысяч черкесов, выжидавших удобного момента для нападения на русский отряд. Через день черкесы, действительно, произвели стремительную атаку на русские войска и сразу расстроили каре Таманского гарнизонного полка, нанеся солдатам значительный урон; но несмотря на одновременную атаку русских войск турками и черкесами, последние в конце концов были опрокинуты на всех пунктах пушечным картечным и ружейным огнем, отступили и не решились больше атаковать русские войска.
В другом сражении солдаты отрезали до 300 турок от отряда, действовавшего за стенами крепости, и, окруживши их со всех сторон, уничтожили их — одних перекололи штыками, а другие, притиснутые русскими к крутому обрыву у моря, бросались в отчаянии с крутизны обрыва и разбивались насмерть о камни. Солдаты при этом выказали необычайное самоотвержение при защите одного из офицеров. Штабс-капитан Томиловский схватился с турецким офицером в рукопашную, поборол его и сбросил в пропасть, но и сам полетел туда же и лишь случайно повис на одном из уступов обрыва. Посланные из крепости турки открыли с берега огонь по висевшему над пропастью офицеру. Увидевши это, два солдата, с риском свалиться в пропасть, пытались подать конец ружья Томиловскому, который от ран не мог стать на ноги и воспользоваться помощью солдат. Один из солдат, от чрезмерного усилия поднять офицера, сам потерял равновесие и упал в пропасть. Оставшийся товарищ стал звать на помощь других солдат. Подбежавшие солдаты сняли с убитых турок пояса, связали их и успели при помощи этого импровизированного каната втащить наверх офицера. В течение всего этого времени раненый Томиловский и герои солдаты были осыпаемы снизу турками градом пуль, и многие оказались ранеными, но офицер был спасен, хотя вскоре и умер от ран.
Турки, однако, продолжали отстаивать крепость, и Меньшиков решил взять ее приступом. В свое время Гудович, взявший Анапу, начал приступ крепости с полевой стороны. Князь Меньшиков избрал для приступа угол с севера крепости, между валом ее и морским берегом, и начал готовиться к приступу с этой стороны, сделав последние приготовления к штурму 10 июня. Увидевши серьезные подготовления к приступу со стороны русских войск и потерявши надежду на помощь черкесов, переставших тревожить русский отряд после битвы 28 мая, когда они понесли огромный урон, турки, по предложению Грейга, вступили в переговоры с русскими. Два дня длились переговоры. Все чрезмерные требования турок были отвергнуты русскими, и 12 июня турецкий гарнизон сдался русским. В крепости оказалось 4 тысячи человек войска и найдено 85 орудий, 29 знамен, 2000 пудов пороха, 25 000 снарядов, 3000 ружей и много другого оружия, а в число пленных попал известный у черкесов и турок Сефер-бей, душа анапского гарнизона. Собственность жителей осталась неприкосновенной, но с этого времени крепость Анапа стала русской.
В рядах войск, осаждавших Анапу и взявших эту крепость, были и казаки Черноморского войска со своим атаманом во главе. По общему отзыву участников в войне, черноморцы при Анапе выказали особое мужество и стойкость, за что и получили знамя с надписью: «За отличие при взятии крепости Анапы 12 июня 1828 года». Сам батька-атаман Безкровный получил за Анапу чин генерал-майора. И было за что наградить эту крупную в истории черноморских казаков личность. Наряду со знанием дела, быстрым соображением, находчивостью и распорядительностью в самых трудных обстоятельствах, Безкровный всегда выказывал необычайную личную храбрость, доходившую до героизма. Поддерживаемый казаками, он лично, в жаркой схватке с неприятелем, отнял у одного из турок богатую турецкую саблю и послал ее в подарок от войска атаману всех казачьих войск цесаревичу Александру, будущему царю-реформатору. При стычках с горцами казачий атаман дрался рядом с казаками и личной своей храбростью всегда воодушевлял других. При малейшей опасности, грозившей кому-либо из казаков, он первым спешил на выручку. И таким он был всегда — и в крупных делах, и в мелких повседневных случаях.