The story of Rewrite centers on Kotarou Tennouji, a male high school student living in the city of Kazamatsuri. Although the narrative ultimately begins on the Moon on October 3, 2010, much of the story follows Kotarou’s daily life in Kazamatsuri. Fascinated by the city's mysteries—particularly rumors of unidentified creatures—he spends his time with five girls in his school's Occult Research Society: Kotori Kanbe, Chihaya Ohtori, Sizuru Nakatsu, Lucia Konohana, and the club president, Akane Senri.

Together, the club members enjoy peaceful days investigating supernatural phenomena and uncovering the secrets hidden throughout Kazamatsuri. Depending on the choices made by the player, Kotarou develops a romantic relationship with each heroine in separate story routes. These routes represent different timelines in which the conflict between Gaia and Guardian unfolds. Despite their differences, each timeline suggests that humanity ultimately faces destruction.

After the completion of the five heroine routes, the story transitions to a devastated version of Kazamatsuri. On the Moon, Kotarou encounters Kagari in a world that exists after a failed re-evolution. At this stage, he has become a unified existence formed from all versions of himself across the various timelines, retaining memories of every world where humanity perished.

Moon Kagari is searching for a method that will allow both Earth and humanity to survive. While she works toward this goal, Kotarou protects her from a massive assault of familiars summoned by Gaia member Sakura Kashima, who is determined to eliminate humanity by killing Kagari. Eventually, Kotarou and the other major characters reunite to defend her. Kagari succeeds in completing her plan by returning the Moon’s life force to Earth. Long ago, Earth had transferred this energy to the Moon so that life there could continue. The restored energy provides just enough resources for one final re-evolution.

Before the main events of the story, Kotarou had served as a low-ranking Guardian member stationed in Kazamatsuri. During that period, he encountered Kagari and, in one timeline, was gravely injured by her. A young Kotori saved his life by using a fragment of Kagari’s ribbon, transforming him into a half-familiar. This process also greatly slowed his aging. Kotarou subsequently fell into a coma and was given drugs that erased his memories of Gaia and Guardian. By the time he awakened, Kotori was already in junior high school. He later graduated alongside her and eventually joined the Occult Research Society in high school. In another timeline, however, Kotarou chooses to let Kagari escape when they meet.

Over time, Kotarou becomes disillusioned with Guardian’s methods and returns to Kazamatsuri, where he encounters Kagari once again. She explains that re-evolution is unavoidable, but that its outcome depends on the memories accumulated by life on Earth. Positive memories born from growth and coexistence could lead to a better future, while memories shaped by war and conflict would result in a dead world.

Determined to help her, Kotarou acts as a double agent, sabotaging both Gaia and Guardian from within. He destroys their operations throughout Kazamatsuri and eliminates members of both factions. When Gaia attempts to force Kagari to begin re-evolution prematurely, a large portion of the city is devastated. Nevertheless, Kotarou succeeds in preventing the plan. Kagari expresses her gratitude, praising him for showing her memories worth preserving. In the end, Kotarou reluctantly stabs Kagari, and after sharing a kiss, the two merge into a sphere of light within a great tree.

Humanity survives the aftermath, though most of the world outside Kazamatsuri enters a severe ice age. Within the city, an enormous tree grows to a height of 500 meters in only three years, housing the orb of light created by Kotarou and Kagari. By this point, the five heroines are high school students and members of the Occult Research Society. Investigating the mysterious tree, they transform Kotarou into a familiar, but he refuses to obey their wishes. Instead, he brings the girls to the Moon, where they discover a small seedling growing from the barren lunar surface. The seedling serves as the embodiment of Moon Kagari, symbolizing the possibility of new life and a hopeful future.