В то же время султан начал восстановление и усиление флота. Зимой 1452 года была осуществлена масштабная программа по строительству кораблей на базе османского флота в Галлиполи, а также, вероятно, в Синопе на Черном море и на других верфях на Эгейском побережье. Согласно Критовулу, Мехмед «полагал, что флоту придется сражаться в первую очередь и он окажет большее влияние на ход осады, нежели армия», поэтому он лично уделял существенное внимание этим работам. У имперских властей появилась возможность использовать большое количество опытных плотников, матросов и кормчих как греческого, так и итальянского происхождения (империя расширила свои владения за счет черноморского и средиземноморского побережий), и квалифицированную рабочую силу можно было задействовать в реконструкции флота. Мехмед также получил доступ к важнейшим природным ресурсам, необходимым для осуществления его попытки: дереву и пеньке, ткани для парусов, чугуну для изготовления якорей и гвоздей, смоле и салу (для отделки и обмазывания корпуса кораблей). Все материалы получали в большом количестве как с территории империи, так и из-за границы. В умении сконцентрировать ресурсы для ведения войны проявился талант Мехмеда-логистика.

Как и в случае с пушками, османы быстро научились строить такие же суда, как у их врагов-христиан. Основным типом боевого корабля в Средиземноморье в Средние века являлась галера, происходившая от римских и греческих галер античной эпохи. Данный вид судов, изменявшийся с течением времени, господствовал на Средиземном море с начала бронзового века до XVII столетия, и кораблям этой модели, чей вид сохранился на минойских печатях, египетских папирусах и вазах классической Греции, суждено было сыграть на протяжении длительного исторического времени такую же важную роль в событиях, связанных с морем, как виноградной лозе и оливковому дереву. К концу Средневековья типичная военная галера была длинной, быстроходной и очень узкой — как правило, около ста футов в длину при двенадцати футах в ширину — с поднятым носом или выступом в передней части, игравшим роль боевой палубы или трапа для перехода на вражеские корабли. Тактика морского боя чрезвычайно отличалась от тактики сражения на суше. Галеры укомплектовывались воинскими командами, которым после первоначального залпа или удара предстояло попытаться атаковать судно противника в жестокой рукопашной схватке.

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

Наряду со всеми преимуществами, которыми обладала галера в спокойном море, она также отличалась исключительными недостатками. Низкий надводный борт служил причиной того, что она совершенно не годилась для плавания даже во время небольшой зыби, свойственной Средиземному морю. Поэтому плавание на галерах, как правило, ограничивалось летними месяцами и диктовало требование держаться берега, а не совершать длинные рейсы по открытому морю. Флоты, состоявшие из галер, нередко тонули в результате несезонных штормов. Паруса можно было ставить, лишь когда ветер дул точно в корму, и сами весла были бесполезны при сколь-либо сильном встречном ветре. Вдобавок требование скорости приводило к тому, что корпус корабля был хрупок и сидел в воде очень глубоко — серьезный недостаток при нападении на судно с высокими бортами, такое как купеческий парусник или одна из больших венецианских галер, которые были гораздо выше. Сильным и слабым сторонам галер пришлось выдержать жестокую проверку в ходе борьбы за Город.

Мехмед собрал большой флот. Он починил и вновь осмолил старые суда и построил некоторое количество новых трирем — галер с веслами, расположенными по три, а также исполненных в уменьшенном масштабе галер для совершения рейдов, «длинных кораблей, быстрых и с полностью крытой палубой, вмещавших от тридцати до пятидесяти гребцов» — европейцы называли их фустами. По-видимому, он контролировал большую часть работ самостоятельно, выбирая «искусных моряков на всех побережьях Азии и Европы — особенно умелых гребцов, палубных матросов, кормчих, капитанов трирем, командующих и адмиралов, и всех прочих, кто нужен был в корабельных командах». Некоторая часть султанского флота находилась в Босфоре уже в марте, переправляя войска через пролив, однако основные силы не могли собраться в Галлиполи ранее начала апреля. Командующим назначили адмирала Балтоглу, «великого человека, опытного адмирала, искусного в деле войны на море». В первый раз за семь осад османы привели к Городу флот, тем самым сыграв чрезвычайно важную роль в ходе военных действий.

Галлиполи, «отечество защитников веры», являлся городом-талисманом для турок и удачным местом для начала похода. (Именно здесь османы захватили свой первый в Европе плацдарм после неожиданного землетрясения.) Моряки были охвачены желанием начать священную войну и осуществить завоевание. Флот вышел из Дарданелл и двинулся вверх по Мраморному морю. Очевидно, команды отправились в путь «с радостными возгласами; гребцы распевали песни; все подбадривали друг друга криками», но на деле энтузиазм мог быть и не столь бурным: многие гребцы, по всей вероятности, христиане, трудились лишь по принуждению. Согласно позднейшему хронисту, «ветер, посланный Богом, гнал суда вперед», но в действительности все могло быть иначе. К этому времени преобладающим стал северный ветер, так что плыть по Мраморному морю приходилось против ветра и течения. Сто двадцать миль до Константинополя представляли собой нелегкий труд для гребцов.

Новость о продвижении галер распространялась по побережью, обгоняя их. Изумление смешалось с паникой. Как и в случае с армией, Мехмед осознал, какой психологической ценностью обладают крупные соединения. Именно вид моря, покрытого веслами и мачтами, повергал в ужас жителей греческих деревень на побережье. Наиболее заслуживающие доверия подсчеты численности османского флота сделали опытные моряки-христиане, такие, как Джакомо Тетальди и Николо Барбаро (их цифры куда достовернее, нежели те, что называли весьма впечатлительные неспециалисты в морском деле). По их оценкам, численность колебалась от двенадцати до восемнадцати полностью укомплектованных военных галер — сюда входили и биремы, и триремы, затем от семидесяти до восьмидесяти фуст меньшего размера, около двадцати пяти парандарий — тяжелых транспортных барж, и некоторое количество легких бригантин и других посыльных палубных судов, что в целом составляло сто сорок единиц. Появившись на западной линии горизонта, они представляли собой поистине устрашающее зрелище.