Kněžka Reimu Hakurei se vrací ze svého tréninku v horách a nachází svojí svatyni zamořenou duchy a dalšími nadpřirozenými bytostmi. Vyzbrojená talismany a Yin-Yang orby se s vervou do nezvaných návštěvníků pustí. Na létající želvě Genjii pak musí nalézt zdroj invaze.

Story of Eastern Wonderland je na rozdíl od prvního dílu čistokrevné danmaku s vertikálním scrollováním. Na shora viděných úrovních ovládáte Reimu a po nalétávajících nepřátelích automatickou střelbou metáte talismany. Na největší skrumáž máte po ruce omezený počet bomb s plošným útokem. Neméně důležité je vyhýbat se nepřátelským projektilům. Každý level se dělí na část s řadovými nepřáteli, kde nabíráte talismany pro silnější útok a skóre, a část s bossem. Reimu a Ganjii s některými nepřátelskými NPC komunikují, nicméně to stejně vždycky skončí bojem.

Story of Eastern Wonderland vyšel společně s prvním dílem a pouze v japonštině.