Нынешняя церковь, вероятно, была начата в 1333 г. Утраченная надпись, ранее находившаяся в арке нефа рядом с левым трансептом, гласила, что эта часть здания была завершена в 1368 г. Надпись явно двусмысленна, поскольку она может относиться как к восточной, так и к западной части церкви. Внимательное изучение строения Гербертом Деллуингом позволило предположить, что весь план здания, возможно, был составлен в одно время, но после возведения нижней части стен было решено довести хоры до завершения в первую очередь. К началу XV в. всё здание было закончено, за исключением внутреннего убранства, например, хоров. Окончательно церковь была освящена в 1430 г. Купол вряд ли был частью первоначального плана, так как пересекающие его опоры – слишком тонкие, а он сам не интегрирован в остальную структуру. Предположительно купол был добавлен в XV в., чтобы подражать высоким куполам церкви Сан-Марко. Он уже появляется на гравюре 1490 г., а также на карте де’ Барбари 1500 г.
План первого этажа демонстрирует ясный, тщательно продуманный замысел. Неф состоит из пяти квадратных пролетов, каждый из которых по размеру равен купольному переходу, двум трансептам и алтарю; боковые нефы в два раза уже центрального. Алтарь имеет многоугольную апсиду, повторяющуюся в меньшем масштабе в двух фланкирующих капеллах по обе стороны. Хотя нельзя утверждать, что у доминиканцев существовал какой-то генеральный план, сходство между планом Санти-Джованни-э-Паоло и планом родственной церкви во Флоренции, Санта-Мария-Новелла, основанной примерно в то же время, показывает, что идеи быстро распространялись по Италии. В своих основных чертах флорентийская церковь отличается от Санти-Джованни-э-Паоло только двумя более короткими нефами, занявшими место пятого квадратного нефа, и отсутствием многоугольных апсид в алтаре и фланкирующих капеллах. Длинный, просторный центральный неф вместе с боковыми нефами, должно быть, произвел впечатление на венецианцев, поскольку базилики Торчелло и Мурано с продольной планировкой, похоже, не имели в городе ближайших потомков. Согласно Франческо Сансовино, даже собор Сан-Пьетро-ди-Кастелло был «в греческом стиле» до перестройки в начале XVII в.
Базилика Санти-Джованни-э-Паоло, план
В таких городах, как Флоренция, церкви нищенствующих орденов были основаны на рыночных площадях, которые образовывали просторные пьяццы для украшения зданий. В Венеции для новых церквей не было таких площадок. Вокруг основанной на острове Санти-Джованни-э-Паоло земля должна была быть понемногу «отвоевана». Г-образный кампо перед зданием слишком мал, чтобы не поразить воображение огромными размерами церкви, которая кажется совершенно несоразмерной с окружающей средой. Когда-то кампо было еще меньше, так как нынешнее расширение вдоль южной стороны было сделано только в XIX в. До этого времени она была перекрыта Скуолой-ди-Сан-Винченцо, зданием, которое можно увидеть на картинах Каналетто. За ней находилось кладбище монахов, еще дальше – Скуола-ди-Сант-Орсола (первоначальное местонахождение знаменитого цикла картин Карпаччо «Жизнь святой Урсулы», хранящегося сейчас в Академии изящных искусств). Однако характерные венецианские материалы – теплый красный кирпич и четкие белые детали из истрийского камня – помогают церкви вписаться в городской пейзаж.
Внешний вид Санти-Джованни-э-Паоло чрезвычайно прост и четко отражает внутреннюю конструкцию. Как и в других больших готических церквях того периода в Италии, усиление обеспечиваются только утолщенными кирпичными опорами, установленными через равные промежутки вдоль наружных стен. Здесь нет никаких летящих контрфорсов, чтобы разгрузить тяжелые контуры массивной каменной кладки. Высокие, узкие, двусветные стрельчатые окна устремлены вверх, как стрелы, усиливая эффект высоты, но почти не нарушая непрерывности массивных кирпичных стен. Узор кирпичной кладки под карнизами – характерный для итальянской готики декоративный мотив, возможно, навеянный оборонительными машикулями на укрепленных средневековых зданиях. Похоже, что первоначальная схема церкви включала в себя сочлененный фасад, но строительство так и не продвинулось дальше самого нижнего яруса, состоящего из ряда глухих готических арок.
Глубокие ниши фасада, вероятно, предназначенные для гробниц, также являются частью доминиканской строительной традиции. Подобные ниши можно найти не только на стенах Санта-Мария-Новелла, но и, что ближе, в доминиканской церкви Эремитани в Падуе, а также во францисканской церкви Сан-Лоренцо в Виченце. Примечательно, что одну из ниш занимает гробница дожа Якопо Тьеполо, пожертвовавшего это место (умер в 1249 г.). Первоначально она стояла перед входом в более раннюю церковь. После щедрого завещания 1458 г. работа над фасадом была возобновлена, но вскоре проект снова заглох. Единственным результатом стал изысканный резной центральный портал с классическими колоннами, поддерживающими тяжелую готическую арку, выполненную в мастерской Бартоломео Бона.