当神社は往昔幾度か火災に遭ひ、古文書は現存しないが社記に依ると「畏くも人皇十二代景行天皇の御代、皇子日本武尊東夷御征定の砌、甲武信の国境を越えさせ給ふ時、靄霧四呎を弁せず依って岩室に山営を張り、三神に祈念を凝し給ひし時、神宣ありて皇子の向ふべき路を示し給ふ。依って武尊神恩奉謝の印として岩室に佩剣を留め給ひ以って三神を斎き給ふ。爾来、大嶽山奥の古院として代々剣を立て、三神を奉斎せり。後人皇四十代天武天皇の御代役の行者小角、富士の霊峯開山を志すに当り木花咲耶媛命の御父神を祭祀し、其の御守護を被り此の大業を完遂させんと従者と共に至り、当山の霊験なるを以て祈誓所修験道場を定めたるに、不思議にも昼夜連日に亘り鳴動止まず、故に神意ならんと単身山頂に至り拝むに神宣有り『我は三神なり』と、小角驚恐して身の置く所を知らず、其れより当山を赤之浦那留都賀崎の大嶽山と称へ奉る。今尚当山東に行者の遺跡存す。養老元年（七一七年）僧泰澄来りて神宣を蒙り藤蔓を以て四面の山頂に七五三を張り、神域を定めて七日七夜篝火を焚き祈?す。又、堂宇を修復なし岩室に参籠なす即ち西の行者の行跡是なり。天平七年（七三五年）僧行基勅令を奉じ諸山歴訪の砌り当山に至り参籠をなし観世音像を刻す時、神感ましまして神威ナガトととかれ、『赤の浦那留都賀崎に那留神の御稜威や高く那賀都とは祈る』と進歌を奉じ、其れより当山を大嶽山那賀都神社と申上奉るとなむ。天長八年（八三一年）僧空海弘法巡錫の砌、登山修業なし弘法の絵書石、清浄の滝、座禅岩の行跡を遺す。文明五年（一四七三）美濃浮洲の城主日原河内守藤原重実霊宣を蒙り、再建し奉る時に、厳寒冷凍斧を振る事不能。然るに深夜大木の倒るヽ音しきりなり。翌朝之を見るに古木、大木伐採山積しありたり。依って神助により工を起し社殿の建立をなす。以来是より薪切祭をなし神慮を慰む。以下略」又甲斐国社記・寺記第四巻寺院編に、由緒書上帳で、山梨郡下石森村羽黒修験観音寺より、甲府市御城代松平伊予守に差出した書面に「甲斐国山梨郡万力筋上釜口村釜戸ノ庄那訶都神社大嶽山金剛坊大権現、社地五町四方余、当神社往古人皇四十四代元正天皇ノ御宇養老元丁巳三月十八日笛吹川ノ源、国司ヶ嶽に鎮座ス。次ニ今ノ社ヘ御遷ノ時鳴動ス夫ヨリ折々鳴動ス。依テ鳴渡カ崎ト呼ビ、今、那訶都ニ依テ国司ガ嶽ハ奥院ト申伝ル。往古日原氏宮之丞トテ社主有シガ聊ノ事有テ大破ニ及、数年来之間小祠有リ。干時宝永中（一七〇四頃）日原氏之二男宮松トテ出生ス。七才ノ時託宣ノ事有テ日々参詣ノ信翼夥シ。元文五庚申年（一七四〇）正月二十一日ヨリ再建ノ企テ東叡山御支配ト成。金剛坊大権現トノ神位御令旨下増益社頭繁栄シ諸堂不残建立ス。拝殿眺望ハ東方ニ川浦観音ノ森、谷底ヲ見渡セハ参詣ノ老若行来ノ人手ニ取ル斗ニ思フ絶景ニシテ岩岨嶮岨シテ数十丈難量中程ニ行者越ト云名有。是ニ少ノ洞穴有、三方ハ流ノ音不絶云々……」と有る。又「本殿九尺四方掛作り、拝殿二間三間掛作り、女人堂四間半八間半中通、本尊伝教大師御作観音壱体、絵馬堂壱丈四方、石鳥居壱丈二尺、末社八社但小祠、馬部九尺四方、雪隠壱ヶ所」明治六年村社に列せらる。同時代には本殿、随神門、神楽殿建替。昭和四十二年拝殿建替。平成二十三年に御鎮座千三百年記念改修事業を敢行し現在に至る。