Budowa Po tym, jak Zakon wyszedł zwycięsko z oblężenia, otrzymał finansową pomoc z Europy, która została spożytkowana na zbudowanie nowej stolicy na półwyspie Sciberras. Papież wysłał włoskiego inżyniera Francesco Laparelliego, aby ten zaprojektował fortyfikacje miejskie, które zostały zaprojektowane jako włoski system bastionów. Oryginalny projekt Laparelliego składał się z otoczonego bastionami rdzenia (enceinte), z dziewięcioma nadszańcami () oraz fosy. Miasto zostało zaprojektowane według systemu hippodamejskiego, miało zawierać arsenał dla floty oraz manderaggio (port dla małych statków).
Kamień węgielny nowego miasta został położony przez wielkiego mistrza Jeana de Valette 28 marca 1566, a miasto zostało nazwane Valletta na jego cześć. Mury miejskie były jednymi z pierwszych konstrukcji budowlanych, postawionych w mieście, i w większości zostały skończone w latach 1570. W trakcie stawiania murów dokonano pewnych zmian w stosunku do projektu, i tylko dwa nadszańce zostały zbudowane, a arsenału i manderaggio nigdy nie zbudowano. Fort Saint Elmo, który został poważnie uszkodzony podczas oblężenia w 1565, został odbudowany i włączony w system murów miejskich.