Несмотря на серьезные проблемы с прикрытием боевых кораблей с воздуха вдали от баз, советский флот мог с полным правом претендовать на господство в акватории Черного моря. Черноморский флот в своем составе насчитывал около 100 надводных кораблей и более 50 подводных лодок. Командовал флотом вице–адмирал Ф. С. Октябрьский, членом Военного совета был дивизионный комиссар Н. М. Кулаков, начальником штаба — контр–адмирал И. Д. Елисеев. Десантные суда специальной постройки в составе флота отсутствовали. Основные силы флота были рассредоточены в базах кавказского побережья: в Новороссийске, Туапсе, Поти, Батуми. Незначительная часть боевых и вспомогательных кораблей находилась в Севастополе. Азовская военная флотилия, которой командовал контр–адмирал С. Г. Горшков, имела до 25 кораблей, базировавшихся на порты Ейск, Ахтари, Темрюк.
План высадки морского и воздушного десантов на Керченском полуострове появился у командования Закавказского фронта еще в конце ноября 1941 г., вскоре после оставления Крыма советскими войсками. Первый доклад с изложением основных идей операции был направлен в Ставку ВГК 26 ноября 1941 г. Предложение было воспринято с интересом, и 30 ноября в Ставку ВГК был направлен развернутый доклад с детализацией плана и расчетом количества выделяемых войск. Первоначально предполагалось овладеть десантом только восточной частью Керченского полуострова и двигаться далее до Феодосии. Директивой Ставки ВГК № 005471 от 7 декабря 1941 г. этот план был утвержден и фронт приступил к его практической реализации. В начале декабря к планированию операции было подключено командование Черноморского флота. В докладе в Ставку ВГК от 6 декабря Ф. С. Октябрьский сразу потребовал не менее 15 дней на подготовку операции и указал на слабости разработанного сухопутным командованием плана. Во–первых, адмирал Октябрьский указал на сложную ледовую обстановку на Азовском море. В зависимости от направления ветра могла сложиться такая ситуация, что весь Керченский пролив окажется забитым торосами и «ни одна посудина не пролезет». Поэтому предлагавшийся армейским командованием вариант высадки основных сил десанта через Азовское море Октябрьский счел нужным отклонить. Во–вторых, в докладе командующего Черноморским флотом впервые появилось название Феодосия. Адмирал Октябрьский предложил высаживаться сразу в двух крупных портах — Керчи и Феодосии. Это могло обеспечить нормальное снабжение высадившихся войск.
К моменту утверждения плана высадки в Крыму оборонявшей полуостров 11–й армии Э. фон Манштейна противостояла располагавшаяся на Таманском полуострове часть сил Закавказского фронта Д. Т. Козлова — 51–я и 44–я армии. Разумеется, из поспешно покинувших Керченский полуостров войск в группировку для сравнительно крупной десантной операции 51–я и 44–я армии превратились не по мановению волшебной палочки. Как и на других участках фронта, усиление армий для активных действий произошло за счет свежесформированных соединений.