Развитие обстановки на южном крыле Восточного фронта и выход Италии из войны принудил к сдаче Кубанского плацдарма. 5 августа группа армий «А» вынуждена была передать в состав группы армий «Юг» 355-ю пехотную дивизию, обеспечивавшую охрану Крыма. В связи с этим командующий группой армий «А» генерал-фельдмаршал фон Клейст приказал вывести с Кубанского плацдарма остатки 13-й танковой дивизии. С 18 по 20 августа 13-я танковая дивизия переправилась в Крым, но там не осталась, а маршем была переброшена на северный берег Азовского моря в состав 6-й армии, которая вела там тяжелые бои. Опасность того, что Крым будет отрезан от остального Восточного фронта, была очень велика. Германия опасалась, что с его потерей из войны выйдет Румыния. 3 сентября командующий группой армий «А» получил из ОКХ приказ оставить Кубанский плацдарм. Первым днем эвакуации должно было стать 7 сентября. Группой армий «А» и 17-й армией заблаговременно были разработаны планы отхода «Кримхильда» и «Брунгильда».
План «Кримхильда» был рассчитан на срок эвакуации 10—12 недель и предусматривал вывоз всего имущества, предназначенного для дальнейшего ведения войны, а также значительного количества гражданского населения.
План «Брунгильда» предлагал провести эвакуацию за 38 суток, вывоз имущества вермахта и приведение в негодность промышленных и других грузов.
Оба плана предусматривали поэтапный отход к Керченскому проливу и ведение временной обороны на выгодных участках местности. При этом особое значение придавалось «Малой голове гота», связанной с Таманским полуостровом только в трех местах. Для отхода должна была полностью использоваться единственная хорошая дорога Киевское — Варениковская. Важнейшим фактором скорости отхода была согласованность с возможностями морских транспортных средств. План предусматривал переправу через Керченский пролив одной дивизии ежедневно.
Штаб армии довел план в общих чертах до управлений корпусов. Его детальная проработка была их делом. За 30 часов до начала каждого отхода они должны были ставить задачи своим дивизиям. Поэтому каждое подразделение должно было знать, когда и куда ему предстоит двигаться.
Для установки заграждений и оборудования промежуточных позиций работало 13 саперных и 11 строительных батальонов. Усиленное наблюдение за черноморскими портами со стороны воздушной и морской разведки должно было заблаговременно выявить приготовления противника к возможной десантной операции.
Приготовления немцев не укрылись и от советского командования. Обе стороны стремились выявить намерения друг друга, но точное время отхода так и осталось для советской стороны тайной.
К этому времени советское командование уже вывело часть своих войск с Кубани и бросило их в бой для развития успеха севернее Азовского моря. Одновременно был замечен перевод десантных средств из южных черноморских портов в Геленджик. Оценка обстановки управлением 17-й армии в ближайшее время не предусматривала крупных боевых действий со стороны противника.
В ночь на 30 августа в порту Новороссийск был захвачен в плен русский лейтенант флота Васильев. Ему была поставлена задача приблизиться в резиновой лодке к берегу и разведать силы немецкого гарнизона и местность между западным молом и Станичкой. В результате его допроса удалось выяснить, что предстоит нападение на внутреннюю гавань, одновременный десант в районе Анапы, Озерейки, высадка воздушного десанта в районе Борисовки и сковывающий удар под Темрюком. Были показания советского лейтенанта правдой или вымыслом? Для обеспечения безопасности 1-й батальон 228-го егерского полка был переведен в порт Новороссийск, а остальные подразделения этого полка приведены в готовность для действий в резерве. Но удара советских войск не было. Резервы были отведены. И все же оказалось, что показания Васильева были правдивыми. Высадка советского десанта два раза откладывалась из-за погодных условий.
Вечером 9 сентября 1943 года соединение десантных кораблей под командованием контр-адмирала Холостякова вышло в море. На них находились отборные части: 255-я бригада морской пехоты полковника Потапова, 393-й отдельный морской стрелковый батальон капитан-лейтенанта Бутылина, носивший почетное наименование «имени Куникова», 1339-й стрелковый полк подполковника Каданчика и другие мелкие подразделения общей численностью 8935 человек на 129 мелких кораблях.
В полночь десантное соединение находилось у входа в Новороссийскую бухту. В этот момент более 800 орудий и минометов, а также большое количество реактивных минометов открыли ураганный огонь по порту и городу. Дальнобойные батареи береговой артиллерии с берега Цемесской бухты поражали цели далеко в -тылу немецких войск.