Prieš trylika šimtų metų, Naros laikotarpiu, imperatoriaus Shōmu prašymu, kunigas Gyōki įkūrė keturiasdešimt devynias Hosso sektos šventyklas, viena iš jų - Saihoji šventykla. Sakoma, kad prieš įkuriant šventyklą, Asuka laikotarpiu, iš pradžių ji buvo viena iš princo Shōtoku vilų.
Ankstyvuoju Heiano laikotarpiu šventykloje laikinai gyveno Kōbō Daishi, tačiau Kamakuros laikotarpiu Hōnenas ją pertvarkė į Džōdo sektos šventyklą. 1339 m., vykstant pokario nuniokojimui, Fudžiwaros Čikahidės (Matsunō šventyklos vyriausiojo kunigo) kvietimu Musō Kokushi, vienas iš labiausiai gerbiamų to meto Japonijos dzen kunigų, atgaivino ją kaip dzen šventyklą.
Nuo to laiko šventyklą lankė daugelis besidominčių dzen praktika, tarp jų - Ašikaga Jošimicė (Ashikaga Yoshimitsu) ir Jošimaša (Yoshimasa). Taip pat sakoma, kad Saihoji šventykla buvo Muromači laikotarpio reprezentacinių šventyklų prototipas ir pavyzdys šventykloms, kuriomis buvo sekama, pavyzdžiui, garsiosioms Kinkakuji (Auksinis paviljonas) ir Ginkakuji (Sidabrinis paviljonas).
Šiuo metu 35 000 kv. m ploto sodas yra įtrauktas į Japonijos istorinių vietovių ir vaizdingo grožio vietų sąrašą, o 1994 m. buvo įrašytas į UNESCO pasaulio kultūros paveldo sąrašą kaip senovės Kioto istorinis paminklas. Šiandien dėl gražių samanų, kuriomis padengta teritorija, ji dar populiariai vadinama Kokedera (samanų šventykla).
