Береги острова Мальти утворюють звивисту лінію, порізану численними зручними бухтами. Ця географічна особливість пояснює чому, на місці сучасної Валлетти люди селилися ще з IX століття до нашої ери, коли острів колонізували фінікійці. Протягом століть Мальта переходила з рук в руки: в VII столітті до нашої ери вона належала грекам, з VI століття до нашої ери — Карфагену, з 218 року нашої ери — Риму, потім її захопили вандали, яких змінили візантійці, а 869 року — араби. Нормани приєднали в XI столітті Мальту до Сицилії. На початку XVI століття імператор Карл V подарував острів ордену госпітальєрів.

Історія Валлетти починається з того моменту, коли нечисленні загони мальтійських лицарів під проводом Жана де Ла Валлетта відбили напад турецьких військ, які направив на завоювання архіпелагу Сулейман Прекрасний. Перемога дісталася жителям Мальти доволі дорого, привівши магістра до рішення створити добре укріплене місто, яке в майбутньому допоможе протистояти натиску ворогів.

Великий магістр особисто заклав перший камінь нового міста 28 березня 1566 року. Щедрі пожертви з усього християнського світу дозволили вести будівельні роботи дуже швидко. Будівництвом керував італійський архітектор Франческо Лапареллі, який розробив план Валлетти та отримав вперше за всю історію містобудування в Європі можливість робити все відповідно до норм і правил архітектури. Було споруджено спеціальні системи для відводу стічних вод і видалення сміття з міста, що дозволило вести роботи, не накопичуючи будівельних відходів. Планування вулиць було спроектовано таким чином, що морський бриз очищав повітря міста, створюючи ефект кондиціонування.

Одразу ж був створений спеціальний Департамент міського планування (існує досі), який жорстко регламентував все, що стосувалося забудови. Департаментом було наказано ставити будинки уздовж однієї лінії, прикрашати їх на кутах скульптурами, а у дворі влаштовувати криниці для збору дощової води, заборонялося розводити сади перед фасадами.

Одночасно зі спорудженням житла та громадських будівель створювалися інженерні оборонні будівлі навколо столиці. За п'ять років ці роботи було закінчено, зокрема було викопано широкий рів, який відділяв Валлетту від основної частини острова. Довжина рову становила 1000 метрів, глибина 18 метрів, а ширина — 20 метрів.

З 1570 року будівництво міста продовжив учень Лапареллі Джироламо Кассар. Під його керівництвом у Валлетті були побудовані палаци і церкви. У Валлетті розвивалася торгівля, ремесла та мистецтво. Розвиткові Валлетти сприяло те, що, позбувшись від загрози турецьких завойовників, мальтійські лицарі незабаром стали піклуватися про комфорт власного проживання та зайнялися будівництвом розкішних особняків та палаців.

1798 року лицарі, які втратили бойовий дух і дисципліну, не змогли, та й не захотіли дати відсіч військам Наполеона. Навпаки, багато хто з них влаштували імператору захоплений прийом, оскільки мали французьке коріння. Така поведінка лицарів допомогла Валлетті уникнути руйнувань та зберегти свій первісний вигляд.

1800 року Валлетта разом з усім островом перейшла в руки англійців та залишалася під їх владою до 1974 року.

Під час Другої світової війни місто зазнало серйозних руйнувань через нальоти німецької авіації.

З 1974 року Валлетта стала офіційною столицею Республіки Мальта, що отримала незалежність.