彦五瀬命は神武天皇ら弟たちとともに東征に向かったが、難波の白肩津での長髄彦との戦闘で負傷した。太陽に向って戦うのは良くないとして、東から回り込むために一行は南下したが、その傷が元で、紀国の男之水門に着いたところで彦五瀬命は亡くなった。紀伊国竈山に墓が作られたと『古事記』にある。『紀伊続風土記』によれば、当所がその竈山の地であり、墓が作られてすぐに、側に神社が作られたとある。
延喜式神名帳では「紀伊国名草郡 竈山神社」と記載され、小社に列している。

　「釜山神社神主職宛行状」（日前宮文書）によれば、永徳元年（1381年）、紀国造家によって鵜飼新五郎が神主に任ぜられた。以降、鵜飼家が神職を世襲していたと見られる。
　天正13年（1585年）、羽柴秀吉の紀州根来衆攻めにより社宝・古文書を焼失し、社領も奪われて荒廃した。慶長5年（1600年）、紀伊国に入国した浅野幸長が小祠を再建し、寛文9年（1669年）、徳川頼宣が社殿が再建した。しかし、江戸時代を通して寺社奉行の支配下に置かれ、氏子も社領もなく衰微していた。
　明治に入り、宮内省管轄の彦五瀬命墓と、竈山神社は正式に区分され、近代社格制度のもとで明治14年（1881年）に村社に列格したが、神武天皇の兄を祀るという由緒をもって社殿が整備され、明治18年（1885年）には官幣中社に、大正4年（1915年）にはついに官幣大社に進むという異例の昇格をした。村社から官幣大社まで昇格したのは当神社が唯一の例である。現在は神社本庁の別表神社となっている。