Несмотря на неоднозначные оценки применения парашютного десанта в ходе высадки морской пехоты Черноморского флота в районе Южной Озерейки в феврале 1943 г., командование флота не только решило сохранить это подразделение парашютного спецназа, но и значительно усилить его, создав на базе прежней отдельной парашютно-десантной роты Отдельный парашютно-десантный батальон в составе четырех рот. Командиром созданного в мае 1943 г. Отдельного парашютно-десантного батальона был назначен майор Н.Д. Алексеенко, начальником штаба – капитан Г.И. Марущак. Сразу же после создания батальона его личный состав начал усиленно готовиться к новым воздушным десантам, но больше десантироваться с воздуха батальону так и не пришлось. Свой последний бой он провел в качестве морской пехоты в ходе высадки тактического морского десанта у мыса Тархан под Керчью 10 февраля 1944 г. Проведение данной десантной операции было связано с предшествующим оперативным Керченско-Эльтигенским десантом в ноябре-декабре 1944 г., который не привел к полному выполнению поставленных перед ним задач: освобождение на первом этапе Керченского полуострова, а затем совместной со 2-й гвардейской и 51-й армиями 4-го Украинского фронта наступательной операции по освобождению Крыма. В результате был только создан небольшой плацдарм к северо-востоку от Керчи и затем освобождено несколько кварталов в северных пригородах Керчи.

Для расширения Керченского плацдарма и полного освобождения города Керчь командующий Отдельной Приморской армией генерал И.Е. Петров поручил штабу своей армии подготовить новую тактическую десантную операцию. Операция была подготовлена спустя месяц после неудачи высадки морского десанта в районе горы Митридат. Возможно, по этой причине события в районе мыса Тархан привлекли к себе особое внимание Ставки Верховного главнокомандования, чей представитель маршал К.Е. Ворошилов непосредственно наблюдал за высадкой и последовавшей затем двухдневной эпопей с наблюдательного пункта западнее местечка Юркино. Кроме него, все это время на НП находились также командующий Черноморским флотом вице-адмирал Л.А. Владимирский и сам командующий Отдельной Приморской армией генерал И.Е. Петров. Для проведения десантной операции моряками Азовской флотилии были подготовлены все имевшиеся в их распоряжении исправные плавучие средства, в том числе около 40 тендеров и мотоботов, несколько сторожевиков и бронекатеров, баркасы и другие малые суда.

Согласно плану новой операции предполагалась высадка основных сил десанта на мыс Тархан. Основной состав этого десанта численностью порядка 3 тысяч человек состоял из 166-го гвардейского стрелкового полка из состава 55-й гвардейской стрелковой дивизии, которым командовал Герой Советского Союза подполковник Г.К. Главацкий, а также 143-го отдельного батальона морской пехоты под командованием капитана Левченко. В качестве дополнительных сил этой десантной группировке под общим командованием подполковника Главацкого были приданы: Отдельный парашютно-десантный батальон ВВС ЧФ под командованием майора Н.Д. Алексеенко и 613-й отдельный штрафной батальон Черноморского флота под командованием старшего лейтенанта Ф.А. Аверченко. Эта дополнительная группировка десанта насчитывала в общей сложности 700 человек. Непосредственная подготовка к участию парашютно-десантного батальона в морском десанте на мыс Тархан началась во второй половине декабря 1943 г., когда его личный состав был переброшен в город Темрюк. Особое внимание при подготовке к новой операции обращалось на обобщение опыта уже проведенных десантных операций в этом регионе, а также на морально-психологическую подготовку к наступательным действиям в условиях сильного огневого противодействия со стороны неприятеля. С личным составом проводились занятия по тактике, тренировки по погрузке подразделений на различные плавучие средства и высадке их на берег. Работали напряженно, днем и ночью, в различных метеоусловиях. Особой заботой командира и штаба была подготовка передового отряда, от действий которого во многом зависел успех батальона. В его состав подбирались лучшие, наиболее смелые и инициативные краснофлотцы и командиры, которые, по всей видимости, должны были усилить боевую устойчивость соединения, имевшего в своем составе не так уж много ветеранов и бойцов, обладавших боевым опытом.