Debido al aumento constante de la población en Mellieha, fue necesario construir una iglesia parroquial más grande. Después de adquirir un terreno, cerca del Santuario de Nuestra Señora de Mellieha, se empezó a construir la nueva iglesia, que después de 14 años se terminó en 1897. Los feligreses se aseguraron de seguir siendo generosos con su nueva iglesia. Los feligreses se aseguraron de seguir siendo generosos con su nueva iglesia. Las pinturas del altar principal y de los altares laterales son obras de los mejores artistas malteses de principios del siglo XX,a saber:Giuseppe Cali, Lazzaro Pisani y Gianni Vella, entre otros.

La parroquia está dedicada a la Natividad de Nuestra Señora, también conocida como Nuestra Señora de la Victoria. La pintura titular muestra la victoria de los malteses y de los Caballeros de San Juan contra las tropas invasoras otomanas en 1565. La pintura muestra a un caballero recibiendo una palma de un ángel, como símbolo de martirio. La parte superior de la pintura muestra a una joven María sentada en el regazo de Santa Ana, que está acompañada por San Joaquín.

La fachada de la iglesia está dominada por dos agujas decoradas. En la parte superior de la fachada se observan varias estatuas. Otras dos estatuas de piedra flanquean la estatua principal de Cristo Rey, que domina la fachada. Los campanarios también están decorados con estatuas. La fiesta se celebra el 8 de septiembre, que también es fiesta nacional en Malta. La estatua titular de madera de Nuestra Señora es obra de un escultor maltés del siglo X. ㅤㅤㅤ