Magia Record Main Story Prologue and Chapter 1
Kyubey introduces the concept of magical girls before a countdown animation plays (based off the Eternal movie). When it finishes, the game cuts to Madoka Kaname, Mami Tomoe, and Homura Akemi fighting the witch Patricia, as seen in Episode 10 of the anime. Homura complains she can't fight on power lines, and is saved from a familiar by Madoka. Mami says the witch is likely to target Homura because she can't move. Patricia then attacks Homura as Mami expected and both Madoka and Mami defend her. Mami creates a ribbon bridge so Homura can stop time and throw bombs at the witch.
When Homura stops time, the screen brightens and she sees a strange girl. The screen darkens again when the girl disappears. Homura tries to understand what happened, but realizes she has to throw the bombs and does so. Time restarts and the witch is defeated. After the barrier disperses, Homura wonders if she just imagined the girl. Madoka and Mami praise Homura's efforts. Suddenly the screen brightens again and Madoka and Mami disappear. The girl reappears and speaks to Homura, telling her: "If you want to change fate, then come to Kamihama City, because magical girls can be saved in this city". Homura asks the girl what she's talking about, but the girl disappears. Homura wonders if she can change Madoka's fate if she goes to Kamihama.
The world returns to normal and Madoka and Mami reappear. Madoka says Homura was spacing out for awhile. Homura claims she was just tired. Mami invites the girls for tea and cake. Homura narrates that this was the first time this happened - even though everything else had been the same as before, the girl appeared. Homura wonders who the girl was, and wonders if she can change the fate of magical girls by going to Kamihama. A curtain appears and rises up to reveal part of a gear-like symbol. There are Runes that read "Bitte Finden Sie Mich" (BITTE FINDEN SIE MICH, German for "Please Find Me") and 2017 (2017). An unknown creature is seen before the title is shown.
Chapter 1: Iroha of the Beginning
Section 1: The Small Kyubey
Iroha Tamaki is a magical girl who has been having strange dreams of a girl at a hospital. (This girl appears to be the one Homura sees in the prologue). She goes to Kamihama City to find the source of these dreams. While tracking a witch, she comes across another magical girl (later identified as Kaede Akino. After saving Kaede from a familiar, Kaede explains the witches in Kamihama are very strong. Iroha claims she went to Kamihama to look for a small Kyubey. Kaede recognizes it, claiming it's been the only Kyubey around recently, and says she saw it in the witch's barrier. Iroha chases down the witch again and finds the small Kyubey, but is attacked by familiars. She falls unconcious and sees a vision of another magical girl, telling her to leave Kamihama.
Section 2: The Magical Girls of Kamihama City
After another dream of a the girl in the hospital, Iroha is awoken by a magical girl named Momoko Togame. Momoko takes Iroha to visit the "Adjuster" of Kamihama. This adjuster is a magical girl named Mitama Yakumo, who is incapable of fighting witches and familiars by herself. Her power let's her enhance the powers of other magical girls by touching their Soul Gems. When Yakumo uses her power on Iroha, Iroha sees the girl in the hospital again. Afterward, Mitama tells Iroha that when she uses her power on another magical girl she can see their past. She then asks Iroha if she remembers her wish. Iroha is shocked to find that she can't. Iroha immediately sets out to find the small Kyubey, believing it has answers.
Iroha then runs into the magical girl she saw at the end of the previous section, Yachiyo Nanami. Yachiyo threatens to chase Iroha out of town, claiming Iroha's too weak the fight the witches there. Iroha says she just wants to find the small Kyubey. The two fight in a battle that Yachiyo wins. Then Momoko shows up to protect Iroha. Yachiyo claims she wants to avoid more deaths, but Momoko says Yachiyo just wants to keep the magical girl population down so she can hunt more witches. Yachiyo says she's being misunderstood and gives Iroha a challenge. If Iroha and Momoko can defeated the Sandbox Witch (Zenobia) before she does, then she will leave Iroha alone. Iroha and Momoko agree.
Section 3: I Saw Her in a Dream...
The three magical girls enter the witch's barrier and fight familiars. Iroha finally finds the small Kyubey. The small Kyubey is incapable of speech, but Iroha somehow understands it anyway. It directs Iroha and Momoko to the witch, which is being overpowered by Yachiyo. However, Yachiyo is willing to give Iroha one last chance and invites her to kill the witch herself. Iroha defeats the witch and Yachiyo admits that she thought Iroha would be fine from the very start. She explains that she was trying to draw out the small Kyubey, which she describes as an irregularity. It turns out that all the Kyubeys in Kamihama have disappeared except for this one. Believing the Kyubey to be dangerous she attacks it, but it is protected by Iroha. When she touches the small Kyubey, Iroha remembers the truth: The little girl in the hospital was her sister, Ui Tamaki, and her wish was to cure Ui's illness.
Iroha wakes up at Mitama's place, having been brought there by Momoko. Iroha explains that she somehow forgot all about her little sister. Mitama wonders if it is the work of a witch. Iroha thinks she might have forgotten other things. Believing there might be a clue in Kamihama, she resolves to stay and find her sister. Mitama points out the memory might be false, but Iroha believes it was real. (The opening animation plays at this point.) Momoko resolves to help Iroha, as does Mitama...for a price. Mitama then asks Iroha to give the small Kyubey a name. This name is entered by the player, though official merchandise calls him Lil' Kyubey. Iroha asks Lil' Kyubey if he will help her find Ui, and he agrees.