日本佛教在臺傳教，最初是從跟隨軍隊的僧侶開始，有淨土真宗本願寺派、真宗大谷派、曹洞宗、真言宗、日蓮宗、淨土宗等六派。僅有臨濟宗妙心寺派不是從隨軍僧侶開始。 1897年5月8日，伊沢紹倫、大崎文溪受臨濟宗教務本所之令來臺視察，由大崎文溪在澎湖建立佈教場。1898年春，足利天應來臺受松本龜太郎資助，在北投建立虞兆庵，作為臨濟宗妙心寺派在臺傳教的起點，其後河尻宗現、高橋醇嶺加入。該年7月6日，虞兆庵因風雨坍塌，傳教受阻。為了繼續傳教，足利天應在1899年夏請梅山玄秀來臺。

梅山玄秀來臺後，先住於劍潭寺，因環境衛生條件不佳，導致陸續有佈教師病逝，遂有於圓山建立新寺的念頭。 建寺的地點由梅山玄秀提出，山號為「鎮南山」。該地是臺灣原住民與漢族的共同墓地。清末時，漳泉望族趁機瓜分，後由板橋林家林熊光購地，贈予建寺。加藤鎮之助所著《鎮南山緣起》記載，1900年6月進行整地建寺時，兒玉源太郎取名「鎮南護國臨濟寺」，為臺灣唯一冠以「護國」之名的佛寺。 當時日本傳來臺灣的佛教宗派不在少數，兒玉源太郎唯獨支持臨濟宗，因其個人信仰與梅山玄秀的私交所致。兒玉源太郎過世後，於1906年7月28日在本寺舉行追悼會；9月10日又舉行滿中會，梅山玄秀宣告繼承兒玉源太郎遺志，接續完成本寺建設。梅山玄秀返回日本歷訪僧俗，成立「福田會」組織，募款籌措建寺基金。1907年7月5日，於本寺舉行對兒玉源太郎供養的聞蓮會時，再徵求建設基金。 本寺由阿部權藏設計。1910年5月，首先完成庫裡（大寮）；10月舉行上樑儀式，1911年11月本堂（大殿）完成，1912年6月20日舉行入佛式啟用。

本寺為日本臨濟宗妙心寺派在臺傳教的根本道場。荻須純道所編《增補妙心寺史──明治以降の妙心寺》，將梅山玄秀在臺開基與佈教表現，當作海外弘法的典範。 妙心寺派在臺傳教可分為三期： 第一期，日治初期（明治時期）到大正初期，妙心寺派致力於趕上早先來臺的其他佛教院派，但據點僅在臺北、澎湖、花蓮。 第二期，大正年間，藉由沈本圓，結合臺灣本土僧人傳教。 第三期，大正末期到二戰結束前，藉由高林玄寶、東海宜誠，將傳教範圍擴展到南臺灣。 清治、日治以來的臺灣佛寺，雖以曹洞宗居多，但日本曹洞宗與臨濟宗妙心寺派在臺傳教有競合關係。大正末期到昭和年間，妙心寺派在臺傳教成功，信徒激增，1937年信眾數量已超越曹洞宗，1942年更高達兩萬六千人。