Мощные оборонительные сооружения стали определяющим фактором при защите гавани и острова в целом. Разбив турецкое войско, победители испытали сильное желание покинуть лежащий в руинах остров. Груды камня на фоне унылого пейзажа вызывали тоску и, более того, сомнение в том, что разоренная земля сможет приобрести хотя бы довоенный облик. Даже великий магистр начал думать о переезде на континент, куда, кстати, отправились многие молодые кавалеры. Однако, вспомнив годы скитаний, унизительные мольбы о помощи, равнодушие сильных мира сего, он решился на возрождение Мальты, доставшейся слишком дорого, чтобы так легко от нее отказаться. Сомнения окончательно отпали, когда из Рима прибыл посланец папы, знаменитый военный архитектор Франческо Лапарелли де Картона. Известный всей Европе в качестве лучшего специалиста по фортификации, он прославился службой у герцога Козимо Медичи и смелыми проектами, вполне достойными ученика Микеланджело. Застав рыцарей в подавленном настроении, он уже через несколько дней представил на рассмотрение капитула детальный план застройки острова. Восковая модель будущей столицы была отправлена в Испанию для получения отзыва короля Филиппа II, и тот после некоторых поправок дал разрешение на строительство. Перед началом возведения фортификационных сооружений нужно было устроить широкий ров между двумя гаванями, чтобы отделить будущий город от основной части острова. По документам тех лет длина его составила 1000 м, глубина – 18 м и ширина – 20 м. Основные контуры построек намечали глинобитные стены и траншеи. Проектом предусматривалось срыть Сцеберрас, но завершить начатую планировку не удалось, поскольку, получив весть о скором нашествии турок, рыцари бросили основные силы на возведение стен. Таким образом Валлетта осталась на холмах и, как выяснилось, к счастью, ведь крутые улочки, сбегающие вниз по склонам горы, составляют характерную и весьма привлекательную особенность города.
Всего несколько лет потребовалось строителям, чтобы завершить работу над созданием круговой оборонительной системы, состоящей из связанных между собой бастионов, равелинов, дозорных башен. Если учитывать объем работ, примитивные орудия и консерватизм позднего Средневековья, то столь короткий срок являлся рекордным. Никогда еще в Европе город целиком не строился по заранее подготовленным планам и чертежам. Его великолепие сложилось из таких составляющих, как единый стиль построек, мастерская работа каменщиков, но главное – однородность удивительно красивого материала, в качестве которого зодчий выбрал золотистый известняк.
Средневековые города возникали сами собой и строились стихийно, без учета природных особенностей. Великий магистр не хотел видеть новую столицу только лишь неприступной крепостью. По замыслу ей надлежало стать символом культурной и созидательной мощи ордена: «Мы – господа, строим великий город для господ». Основной рабочей силой выступали, конечно, не кавалеры. На ближайших к побережью холмах круглыми сутками копались тысячи наемных рабочих, прибывших из Сицилии и окрестных селений. Время прокладки улиц настало только после того, как поверхность площадки была выровнена, а почва осушена.
После отъезда Лапарелли право продолжать строительство перешло к его местному ученику Джероламо Кассару. Подобно итальянцу, смелый и талантливый, он с одинаковым мастерством сооружал общественные здания, храмы и дворцы с огромным количеством залов, уютных покоев, с тайными переходами и подземными конюшнями. Заслуги мальтийского зодчего перед орденом впоследствии были увековечены в названии одноименной улицы Валлетты, изящной дугой огибающей бастион Святого Джеймса. В условиях обилия средств постройки вырастали очень быстро, ведь папа разрешил трудиться даже в праздничные дни. Глава ордена работал наравне с остальными, выполнял обязанности каменщика и плотника, разделяя трапезу с мастерами. Когда закончились деньги, он приказал отчеканить монеты с изображением соединенных рук, олицетворявших дружбу и согласие. Получив очередной дар, гроссмейстер сумел обменять медные монеты на серебро и золото, заслужив тем еще большее уважение.
Де ла Валлетт заложил первый камень в основание будущей резиденции в 1566 году, а спустя 5 лет его преемник Пьер дель Монте совершил торжественный въезд через главные городские ворота. После праздничной мессы глава ордена направился на обед к племяннику Евстахио в сопровождении свиты и всех рыцарей. Следующий день был посвящен поиску места для жилища великого магистра. По слухам, дворец возвели на участке, предоставленном ордену знатным мальтийским семейством. Земля досталась братьям в вечное пользование за символическую плату в 5 зерен пшеницы и стакан воды из колодца; позже этот источник оказался в центре внутреннего дворика.