The Toindo was built during the early eighth century at the request of Imperial princess Kibi for the repose of the soul of her mother, Empress Genmei (660–721). The hall, a National Treasure, originally stood on the east side of the temple complex, hence its name. It was rebuilt in 1285 facing southward before being reconstructed in 1733 in its current orientation facing west, possibly for auspicious reasons. While the floors of temple halls are often earthen, Toindo has wooden flooring. It also has served as a hall for Zen meditation and at one point was renamed Toin Zendo. Each of these factors has contributed to it being known as the oldest extant Zen meditation hall in Japan.
Like the Large Lecture Hall (Daikodo), the Toindo features a hip-and-gable (irimoya-zukuri) roof, which arrived in Japan from China in the sixth century and has been used in temple and shrine architecture ever since. The gables usually provide protection for the core, or moya, of the building, while the hip roof covers raised aisles (hisashi) that run around the outside of the core. The roof itself is covered by the traditional tiling method known as hon kawarabuki composed of broad, flat concave tiles linked by semi-cylindrical convex tiles. The base of the building is raised to protect the structure from flooding and dampness.