On commença la construction de l'église au XIème siècle. La tradition assure que les Templiers ont contribué, mais leur ordre n'a été fondé qu'en 1118, donc au 12ème siècle. Il est certain qu'ils ont pris part à sa finition et que leur cri de ralliement, "Montjoie", en souvenir de la prise de Jérusalem en 1099 par les Croisés, est peut-être l'origine du nom de la paroisse et du culte dédié à Notre Dame de Joie.

    Dans les anciennes archives, en 1367 on trouve Breulevenez, puis en 1372 Brellevenez , en 1385 Brelevenz (brè = colline). Comme il n'y a pas de véritable éminence terrestre en ce lieu, le vocable ne veut rien dire mais doit être pris dans le sens d'une hauteur spirituelle (à rapprocher de Brelevenez dans les Côtes-du-Nord qui elle, est surèlevée, car levenez veut dire joie en breton, mais dans le dialecte Vannetais parlé à Merlevenez, la commune s'appelle Borhleuiné et se dit encore de nos jours borh = bourg et lèuiné = joie. Une autre explication est: merch = fille et léuiné = joie, qui donne fille de la joie.

    Les Ducs de Bretagne portèrent intérêt au magnifique sanctuaire (élevé en ce lieu pour quelle faveur ou quelle merveille ? Une tradition populaire dit qu'un seigneur marié depuis longtemps et sans enfant promit à la vierge une chapelle et obtint une fille), en particulier, et par l'intermédiaire des seigneurs de Kermadio, ils ont contribué à sa construction sur leur terre. En 1304, l'un d'eux fût héritier légataire du Duc Jean II. Les seigneurs de Kermadio avaient droit de préséance et de sépulture dans l'église. D'autre part, la tradition parle d'un Prieuré des moines de l'ordre du Temple à Merlevenez et de souterrains qui relieraient l'église à kergatorne et à Kermadio. Légendes ou vérités ?

    Au cours des siècles, la première église subit quelques transformations mais le plan est resté pratiquement le même depuis la fin du 12ème siècle. Au 14ème siècle, on commença à monter une tour octogonale sur le carré du transept, et l'édifice fut surélevé au 15ème siècle. On relève aussi la charpente en 1410. La flèche du clocher fut frappée par la foudre en 1533, et reconstruite. Au 18ème siècle, des rétables en bois peints, avec des niches pour St Jean Baptiste et St joseph cachèrent les verrières du choeur et des croisillons, car pendant la révolution, des vandales les avaient saccagées, avaient détruit les vitraux et brulé la toiture. A la fin du 19ème siècle, des réparations importantes furent effectuées et dégagèrent les piliers et les murs de la chaux qui les badigeonnait. L'église retrouva presque toute sa beauté et de nombreux touristes l'ont admirée et photographiée.