W 1557 roku Jean Parisot de la Valette po objęciu urzędu wielkiego mistrza postanowił wzmocnić obronę na Sciberras, wznosząc umocnienia wokół całego półwyspu i budując na nim miasto. Jednak ze względu na brak funduszy i atak wojsk tureckich w 1565 (Wielkie oblężenie), prace te rozpoczęto dopiero w 1566. Kamień węgielny pod budowę miasta, nazwanego na cześć jego założyciela Valletta, został położony 28 marca 1566.
Projekt miasta stworzył, przysłany przez papieża Piusa IV, włoski architekt, uczeń Michała Anioła, Francesco Laparelli. Układ ulic został oparty na planie hippodamejskim, ulice przecinają się ze sobą pod kątem prostym. Całe miasto zostało otoczone szeregiem umocnień, oraz dodatkowo od strony lądu fosą. Ze względu na wysokie koszty i brak czasu (obawiano się ponownego ataku Turków) nie zniwelowano półwyspu, w związku z czym część ulic została zastąpiona schodami. Miały one jednak niskie i długie stopnie, co umożliwiało poruszanie się po nich rycerzom konno, bądź w ciężkich zbrojach.
Pierwszym budynkiem Valletty był kościół Matki Bożej Zwycięskiej, w którym w 1568 pochowany został Jean Parisot de Valette (później grób przeniesiono do konkatedry św. Jana).