勝尾寺の歴史は奈良時代の神亀四年（727）まで遡り、善仲と善算という双子の僧侶が、この霊山で草庵を構え「弥勒寺」を建立されたことに始まります。
平安時代、清和天皇の御世、当山の6代目座主であった行巡上人が、病に臥せっておられた帝の玉体安穏を祈ったところ、その著しい効験に感銘を受けられた清和帝自らが「この寺の持つ法力は、この国を治める王（帝）である私に勝った」として、王に勝った寺、勝王寺（かつ・おう・じ）と命名されました。
しかし、寺側は「王に勝つ」などは余りにも畏れ多いとし、「王」の字を「尾」に差し替え、呼び名はそのまま勝尾寺（かつ・おう・じ）と称するようになりました。
その後、鎌倉時代、戦国時代、江戸時代…と、「勝利を掴む寺」「勝ち運を授かる寺」として、源氏や足利、豊臣、徳川将軍家など時代の覇者たちのみならず、農民や商人らの幅広い信仰を集め、現在では仕事、商売、受験、病気、スポーツ、芸事、選挙、対人関係、恋愛など、人生あらゆる場面での「勝ち運」参拝者で賑わっています。