Анапа же по окончании Крымской войны была вновь занята русскими войсками, которые вошли в нее 10 июля 1856 г. Отряд Сефер-бея отошел в Новороссийск, где продолжил сопротивление. Так, 22 июля 1857 г. его отряд опять пытался взять Анапу, но гарнизон, которым руководил майор Ф. Ф. Левашов, отразил нападение горцев. Однако, выполняя решения Парижского мирного договора, Россия была вынуждена ослабить свое присутствие на побережье. Царским указом 31 марта 1860 г. города Анапа и Новороссийск были упразднены, а в 1862 г., в связи с переносом линии укреплений в междуречье Большой и Малой Лабы и Белой, были упразднены и черноморские укрепления, включая Анапу, которая становится теперь поселком.
После окончания Крымской войны русским войскам удалось активизировать свои действия на Восточном Кавказе и сломить сопротивление сил Шамиля. Узнав о пленении имама Чечни и Дагестана, прекратил свою деятельность среди черкесов и Мухаммед-Амин. В 1859 г. умирает Сефер-бей. Однако, лишившись лидеров, черкесские племена Закубанья не сложили оружия. Русское командование на Кавказе перебрасывает основные силы на левобережье Кубани.
В сентябре 1861 г. на Кубань совершил поездку император Александр II. Он встретился с представителями племен шапсугов, абадзехов и убыхов и, ясно обозначив цели укрепления России на Кавказе, предложил им дать согласие на прокладку через территории, занятые ими, дорог к Анапе, Новороссийску и Туапсе. Однако черкесская делегация отрицательно отнеслась к предложениям русского царя и потребовала отказаться от планов прокладки дорог, строительства укреплений и основания казачьих поселений на их землях.
В ходе последующих военных операций под командованием генерал-адъютанта Н. И. Евдокимова русские отряды привели к покорности натухайцев (i860 г.), шапсугов и абадзехов (1863 г.), убыхов (1864 г.). В целях ослабления горского движения царское правительство начало политику переселения черкесов с побережья Черного моря. Из-за принуждения русских властей и агитации турецких эмиссаров в течение 1858-1865 гг. в Турцию было вывезено около 493 тыс. человек, из них натухайцев - 45023 чел., абадзехов - 27337 чел., шапсугов - 165626 чел., убыхов - 74567 чел. В целях осуществления контроля за ходом выселения черкесов и соблюдения правил выдачи им пособий при отправке в апреле 1864 г. был определен ряд доверенных лиц, наблюдавших за этой процедурой. Среди них был и полковник Фадеев, направленный с этой миссией в Анапу и Новороссийск.
Одновременно с вытеснением горцев царское правительство организовало заселение этих земель казаками Кубанского, Донского, Азовского, Терского и Уральского казачьих войск и крестьянами-переселенцами из Центральной России. 10 мая 1862 г. было высочайше утверждено «Положение о заселении предгорий западной части Кавказского хребта Кубанскими казаками и другими переселенцами из России». §1 Положения гласил, что «предгория западной части Кавказского хребта занимаются казачьими станицами, с целью окончательного покорения горских племен, остающихся нам враждебными», а §2 определял границы территорий, подлежащих заселению, и в состав их входил «берег Черного моря, от устья реки Мокупсе до устья р. Кубани». Интересно, что §6 определял и сроки проведения этой кампании: «Время, потребное для заселения всего пространства, в §2 означенного, будет зависеть от успехов нашего оружия. Если же сильного сопротивления со стороны неприязненных племен не встретится, то заселение предполагается исполнить в течение 6-ти лет». Переселенцы на эти территории наделялись землей: «предварительно для каждой станицы соразмерно с ее населением и сообразно с местностью, отводить от 20 до 30 десятин на каждую душу мужского пола казачьего семейства и по 200 десятин на каждое офицерское семейство удобной и неудобной земли» (§67), и «обязанности строевых частей в продолжении первых трех лет водворения на передовых линиях состоят исключительно в защите собственных станиц» (§64).
В соответствии с этим Положением в 1862 г. идет заселение и Натухайского округа, на землях которого с наряду уже основанными ранее станицами Благовещенской и Витязевской появляются станицы Анапская, Варениковская, Верхне-Баканская, Гостагаевская, Крымская, Натухайская, Неберджайская, Нижне-Баканская, Новороссийская и Раевская. Выбором мест для станиц и организацией их заселения руководил начальник Натухайского округа генерал-майор П. Д. Бабыч. Командующим войсками Кубанской области графом Н. И. Евдокимовым было принято решение на месте разрушенной крепости Анапы образовать поселок, насчитывающий до 50 дворов, и заселить его азовскими казаками.