Il-Karmelitani billi bdew jaraw li n-nies kienet inġibdet wisq lejhom, u li permezz tagħhom id-devozzjoni lejn il-Madonna tal-Karmnu kienet tferrxet ġmielha fost il-Maltin, xtaqu li jibnu kunvent ieħor fil-qalba tan-nies ħalli jkunu jistgħu jferrxu d-devozzjoni tal-Labtu Mqaddes.
Għalhekk, appena bdiet tinbena il-Belt il-ġdida wara ir-rebħa tal-Assedju l-Kbir, Patri Ġwann Vella, Karmelitan, għamel talba lill-Ordni tal-Kavallieri biex jaghtuħ biċċa art biex fuqha jibni kunvent u knisja ddedikati lill-Madonna tal-Karmnu. Il-Granmastru Pietro del Monte laqa’ din it-talba u fis-27 ta’ Lulju 1570 sar il-kuntratt tal-għoti tal-art.
F’dik is-sena stess, Patri Ġwann Vella beda x-xogħol tal-bini tal-knisja taħt it-tmexxija tal-inginier tal-Ordni, Ġilormu Cassar. Sakemm tlesta x-xogħol kollu n-nies kienet tinqeda b’kappella żgħira proviżorja. Il-knisja damet tinbena 38 sena u tlestiet fl-1608. L-ordni tal-kavallieri għen ħafna billi diversi kavallieri bnew il-kapelli laterjali.
Fil-Vista Pastorali ta’ Monsinjur Dusina li saret fi Frar tal-1575 insibu deskrizzjoni dettaljata tal-knisja proviżorja li kienet tintuża sakemm tlestiet il-knisja ta’ Ġilormu Cassar. Din il-knisja kienet iddedikata lil Marija Annunzjata u kienet isservi tal-ewwel Parroċċa fil-Belt. Bil-permess tal-Pirjol tal-Karmelitani, il-Kappillan ta’ Ħal Qormi kien jamministra s-Sagramenti Mqaddsa f’din il-knisja. Don Teramo Balzan għamel żmien jamministra s-Sagramenti Mqaddsa lin-nies tal-Belt Valletta mill-knisja tal-Karmelitani, li allura kienet qed taqdi lin-nies tal-Belt il-ġdida bħala parroċċa.
Il-knisja mibnija minn Ġilormu Cassar kienet ta’ għamla sempliċi: b’nava waħda mdaqqsa u bil-kappelli laterali u għaxar artali. Kienet twila 150 pied u 50 pied wiesa’, u fuqha kellha koppla għamla baxxa u kampnar. Din il-knisja kienet ġiet ikkonsagrata fis-6 ta’ April 1886 mill-Amministratur Appostoliku, Monsinjur Antonio Buhagiar. Is-saqaf tal-knisja, flimkien mal-koppla, l-koppletti u l-kappelli kienu tpittru bejn l-1703-1705 minn Raimondo de Domenicis u Filippo del Palazzo, iżda fl-1743 is-saqaf kien ħass sewwa b’terrimot li kien sar, u l-pittura ġarrbet bosta ħsarat. Fis-seklu għoxrin kienet reġgħet tpittret mill-ġdid minn Ramiro Calì. Fl-4 ta Marzu 1942, fit-Tieni Gwerra Dinjija, waqt wieħed mill-attakki li saru fuq il-Belt Valletta, din il-knisja ntlaqtet u ġarrbet ħsara konsiderevoli fil-knisja b’mod speċjali fil-kor.
Il-proġett tal-bini tal-knisja l-ġdida beda fit-30 ta’ April 1958, meta l-Ġeneral tal-Patrjiet Karmelitani qiegħed l-ewwel ġebla tal-knisja l-ġdida li kellha tinbena fuq pjanta ta’ Ġużè Damato. Ix-xogħol fuq il-bini spiċċa fil-15 ta’ Ġunju 1981, meta l-provinċjal Patri Manwel Gatt bierek din il-knisja wara tlieta u għoxrin sena ta’ ħidma kbira.
Il-Knisja tal-Karmnu, isservi ta’ l-Ewwel Parrocca tal-Belt
Bir-raġun kollu nistgħu ngħidu li l-ewwel Beltin saru Nsara u konfermati fil-Griżma tal-Isqof fis-Santwarju tal-Karmnu tal-Belt Valletta.
Din hija lista ta’ kappillani li servew f’dan is-Santwarju meta serviet ta’ parroċċa tal-Belt Valletta bejn Diċembru 1570 sa Dicembru 1582; Dun Marjanu Briffa, Dun Teramo Balzan, Dun Gaspare Prat, Dun Nikol Burlò, Dun Xmun Blanco, Dun Anton Inguanez, Dun Nikol Bonnici u Dun Sebastjan Cuscusu.
F’Diċembru 1582 meta tlestiet il-knisja ta’ San Pawl Nawfragu saret purċissjoni unika. Iż-żjut Imqaddsa u s-Santissimu Sagrament ġew meħuda uffiċjalment mill-Karmnu sa San Pawl f’purċissjoni solenni li fiha ħa sehem il-kleru l-Ordni ta’ San Ġwann.