"Magia Record: Puella Magi Madoka Magica Another Story" is a manga adaptation of the mobile game "Magia Record," set in the universe of "Puella Magi Madoka Magica." The story takes place in Kamihama City, a location distinct from the original series, where magical girls are drawn by rumors of a mysterious power that can save them from their inevitable fate. The narrative centers on Iroha Tamaki, a magical girl searching for her missing younger sister, Ui. Iroha’s journey intertwines with other magical girls, each grappling with their own struggles and desires.

As Iroha explores Kamihama City, she encounters a diverse cast of characters, including Yachiyo Nanami, a veteran magical girl who initially resists forming connections due to past tragedies. Yachiyo’s aloof demeanor gradually softens as she joins Iroha’s quest. Other key characters include Tsuruno Yui, a cheerful and confident magical girl; Felicia Mitsuki, a brash and impulsive fighter; and Sana Futaba, a shy and reserved girl who struggles with self-worth. Together, they form a group to uncover the secrets of Kamihama City and the enigmatic "Rumors" that grant magical girls unusual powers.

The plot delves into the darker aspects of the magical girl system, exploring themes of sacrifice, despair, and the consequences of wishes. Kamihama City’s unique environment allows magical girls to avoid the tragic fate of becoming witches, but this comes at a cost. The story reveals the existence of the "Wings of Magius," a secretive organization that manipulates magical girls and spreads the Rumors to achieve its own mysterious goals. As Iroha and her allies uncover the truth, they must confront the moral complexities of their choices and the true nature of their powers.

The manga expands on the lore of the "Madoka Magica" universe, introducing new mechanics such as the Doppel system, which allows magical girls to channel their despair into powerful alternate forms without fully transforming into witches. This system becomes a central element of the story, highlighting the tension between hope and despair. The narrative builds toward a climactic confrontation with the Wings of Magius, as Iroha and her friends strive to protect their loved ones and find a way to break the cycle of suffering that defines their existence.