Совершенствование навигационных инструментов сопровождалось значительным прогрессом в кораблестроении. В средневековый период окончательно оформились две различные традиции: распространенные на Балтике и на побережье Атлантического океана когги, при строительстве которых сначала формировали форму корпуса досками обшивки, а затем уже вставляли внутрь каркас, и корабли Средиземноморья, строительство которых начинали с возведения каркаса и лишь затем накладывали на него обшивку. Каркасные корабли Средиземноморья могли достигать внушительных размеров. В генуэзском подряде на строительство судна от 1268 года указывается, что длина корабля должна составлять тридцать семь метров, а ширина по верхней палубе — девять. Самым существенным недостатком таких больших судов был их трудноуправляемый латинский парус. Хотя корабли с латинским парусным вооружением могут ходить круче к ветру, чем суда с прямыми парусами, на них нельзя уменьшить площадь паруса, подвязав его к рею. Вместо этого требовалось спустить рей, снять большой парус и привязать другой, поменьше. Даже смена галса была трудоемким процессом: для этого требовалось опустить рей — достигавший в некоторых случаях пятидесяти метров в длину — на палубу, обнести рей вместе с парусом вокруг мачты и снова поднять его с подветренной стороны. Для управления таким судами требовалась большая команда.

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

Примерно тогда же, когда нао стали основными грузовыми перевозчиками своего времени, а также грозными военными кораблями, появились узкие и более универсальные каравеллы, которые произошли от кариба — небольшого универсального судна, распространенного в основном в Северной Африке и на Пиренейском полуострове. Самое раннее упоминание о каравелле относится к XIII веку, хотя нет никаких данных о ее парусном вооружении или размерах, а сведения о ее дальнейшем развитии очень отрывочны. В начале XV века каравеллы, по-видимому, были преимущественно двухмачтовыми с косым парусным вооружением, но к середине столетия, когда они стали широко использоваться в Португалии и на юге Испании, их начали строить с тремя мачтами. Оснащенная прямыми парусами на фок-мачте и грот-мачте и латинской бизанью каравелла-редонда лучше всего ходила при попутном ветре, а благодаря бо́льшей пропорции длины к ширине была маневреннее каракк. Неудивительно, что расцвет каравелл и каракк совпадает с периодом активного освоения Атлантики, начавшегося под покровительством Генриха Мореплавателя, и достигает вершины во время экспедиции Колумба. Эти суда стали предшественниками кораблей с прямыми парусами классической европейской эпохи парусов, обычно отсчитываемой с конца XVI века.