После победы над турками и снятия осады Гроссмейстер Мальтийского Ордена Ла Валетт превратился в главного героя всей христианской Европы. Но его это не волновало, поскольку главной заботой было восстановление разрушенных укреплений, поскольку предполагалось, что турки могут снова атаковать Мальту. Кроме того, он вынашивал планы строительства новой столицы и штаб-квартиры Ордена Св. Иоанна, место для которой было выбрано на холме Скиберрас. Мысли о строительстве высказывались графом Строцци, ранее первым предложившим строительство форта Сент-Эльмо, и Антонио Феррамолино, проводившего перепланировку форта Сан-Анджело и строившего укрепления Биргу, ныне называющегося Витториоза. Но это не умаляет заслуг самого Ла Валетта, претворившего эти идеи в жизнь.Главной проблемой были финансы. Пользуясь моментом, Гроссмейстер обратился за помощью к христианским государям и получил положительный ответ. Французский король дал ему 140 тыс. ливров, Филипп II Испанский – 90 тыс., король Португалии пообещал 90 тыс. крузаду. Папа Римский пожертвовал 15 тыс. крон и кроме денег прислал инженера Франческо Лапарелли с планами нового города и его укреплений.

Кроме того, и сами Рыцари делали взносы из личных средств, а те, кто не имел наличных средств, предоставляли различный инвентарь.К строительству приступили, не теряя времени зря, и первый камень в основание новой столицы лег 28 марта 1566 г. На него была нанесена памятная латинская надпись, гласившая о том, что новый город будет носить имя Ла Валетта в ознаменование его выдающихся заслуг перед Орденом и народом Мальты. Все Рыцари принимали участие в строительстве. Те, что располагали собственными судами, привозили различные материалы из Италии и с Сицилии, другие посылались в Европу, в частности в Лион за новыми пушками. Большинство же руководило рабочими, которых на строительстве было 8000 чел. Сам Ла Валетт проводил на строительстве целые дни. Первым зданием, возведенным в новом городе, была церковь Св. Девы Побед, где Ла Валетт завещал себя похоронить.Несмотря на все внимание, уделявшееся строительству, трудности возникали. Некоторые выплаты задерживались. Ла Валетт компенсировал это, выпустив специальную бронзовую монету с изображением рукопожатия и надписью «Не деньги, но доверие» («Non aes sed fides»).

Эти монеты раздавались рабочим, когда наличных средств было недостаточно, а позже их меняли на настоящие деньги. Такая система работала, и строительство шло без проволочек.Одним из важных последствий победы над турками стало окончательное сближение мальтийцев с Орденом. Теперь мальтийцам разрешалось занимать ответственные должности в казначействе, суде и магистратах. Потепление отношений наступило и в среде мальтийской аристократии. Рассматривалась возможность для ее членов вступать в Орден. Этого, однако, никогда не случалось, возможно потому, что Рыцари все еще сторонились какой-либо «сарацинской примеси», полагая, что кровь старых мальтийских родов перемешана с мусульманской.В ожидании нового турецкого нападения галеры Ордена были отремонтированы, заново оснащены и посланы в рейд на пути снабжения турок.

Испанский король прислал 15000 солдат для усиления гарнизона острова, на то время пока укрепления не восстановят. Но новой турецкой атаке не суждено было состояться, хотя разгневанный поражением султан Сулейман собирался лично ее возглавить. Летом 1566 г., когда строительство Валетты шло полным ходом, Гроссмейстер получил сведения от шпионов о новых военных приготовлениях турок. Ими строились новые галеры и галеоты. Ла Валетт, боясь не успеть отстроить укрепления, и не желая дольше оставаться в тревожном ожидании, действовал решительно и организовал со своими диверсантами поджог арсенала в Константинополе. Огонь распространился на склады и доки и спалил многие из строящихся кораблей. Это вынудило султана отложить планировавшееся нападение на Мальту и заняться венгерскими делами. Но при осаде Сигетвара 5 сентября 1566 г. султан Сулейман умер. Наследовавший ему сын Селим предпочел нанести удар не по Мальте, а по Венеции.

Используя передышку, Ла Валетт мог теперь решать многочисленные проблемы, возникавшие перед ним, начиная от инженерных сложностей строительства нового города, и заканчивая нарушениями дисциплины молодыми Рыцарями. Укреплению дисциплины и субординации Ла Валетт придавал огромное значение и считал, что без этого будущее Ордена невозможно.Но здоровье Гроссмейстера уже было подорвано. В июле 1568 г., проведя целый день под жарким мальтийским солнцем, он получил солнечный удар и почувствовал, что конец его близок. Ла Валетт привел свои дела в порядок, отдал последние распоряжения, дал свободу своим рабам и амнистировал своих врагов. Он умер 21 августа 1568 г. и был похоронен в городе его имени в церкви Св. Девы Побед. С ним ушла самая яркая эпоха в истории Мальтийского Ордена.Новый Гроссмейстер итальянец Пьетро дель Монте (1568-72 гг.) был уже пожилым человеком. Он не ставил задачу жесткого контроля дисциплины и больше уделял внимание строительству Валетты.

Он планировал выстроить новые подворья для национальных подразделений Ордена «Языков», восстанавливая систему жизни Ордена, складывавшуюся еще на Родосе. Предполагалось, что так можно будет ограничить нежелательные контакты Рыцарей с остальным населением. Этого, конечно, сделать не удалось, но Рыцари теперь имели лучшие условия внутренней жизни, чем в тесных помещениях Биргу.