A Paróquia Nossa Senhora de Fátima dos Mulenvos de Cima, foi fundada sobre os alicerces das Irmãs de São Francisco de Sales (Irmãs Salésias), de modo especial pela Irmã Francisca, Salésia, procuradora do terreno da então igreja paroquial, com apoio da Sociedade dos Missionários da Boa Nova, na pessoa do Padre Laurindo Neto que tanto desejava erguer uma paróquia com o Nome “Paróquia Nossa Senhora de Fátima”.

Em 2004, foi presidida a 1ª Celebração Eucarista nos corredores da escola acima referida, mais tarde as Missas passaram a ser celebradas no Onjango, recem-construída pelas Irmãs Salésias, dentro da mesma escola.

A procura da palavra de Deus foi crecendo em proporção da Evangelização que as Irmãs Salésias exerciam na área com a ajuda dos poucos catequistas que existiam.

Em 2005 o povo da Comunidade nascente cresceu, mas não podia caminhar por si só, Deus abençoou o seu povo e o ímpeto tornou-se cada vez maior. A catequese era assumida pelas irmãs Salésias (Irmãs de São Fracisco de Sales) na sua maioria.

Desta feita nasceram duas comunidades de fé, nomeadamente: São Lucas e Nossa Senhora de Bom Conselho, que eram coordenadas pelos leigos: Severino Jamba e Eugénio Sachimbombo respetivamente, este último já falecido em Setembro de 2006, tendo sido substituido pelo catequista Fernando Silva.

Face ao crescimento da Evangelização e simultaneamente da população, Deus fez brotar os peimeiros sacramentos de iniciação e consequentemente, no dia 23 de junho de 2006, celebrou-se o primeiro matrimónio do Irmão António Felipe Xavier com a Teresa Lina Xavier que veio a desempenhar o cargo de coordenador do Centro Beata Liduina na fusão das duas Comunidades referidas, a partir do dia 2 de junho de 2006, tomou posse perante o Padre António Valente, depois passou a coordenador do Conselho paroquial até 2017, altura que deixou a coordenação por motivo de doença.

Sendo assim, a primeira pedra da Igreja foi lançada aos 7 de Setembro de 2006, pelas 17:00 horas, pelo Padre Laurindo Neto. Em seguida deu-se a construção do alicerce e o fabrico de blocos, iniciando assim a empreitada da Igreja. De lá para cá, a edificação da igreja continuou até o seu término.

Nos anos seguintes surgiram mais comunidades de fé: A Comunidade de fé do Imaculado Coração de Maria, fundada aos 06 de Julho de 2005, foi transferida ao Centro Cristo Rei para fazer parte ao Centro Beata Liduina, em 2017.

Em 2008, foi fundada a Comunidade Nossa Senhora dos Peregrinos, actualemente Nossa Senhora do Rosário, constituindo assim, 04 (quatro) Comunidades de Fé, sendo elevado a zona pastoral Nossa Senhora Rainha aos 23 de Novembro de 2009 até 2011 e depois passou a chamar-se Nossa Senhora Imaculada Conceição.

Aos 12 dias de Fevereiro de 2012, a Igreja ainda em construção ascendeu a categoria de Paróquia Nossa Senhora de Fátima, sendo seus primeiros párocos Frei Ângelo José Luis e Frei António Boaventura Zovo Baza.