Eine Mittelschülerin namens Madoka Kaname und ihre beste Freundin Sayaka Miki treffen auf ein kleines, katzenartiges Wesen namens Kyubey. Kyubey bietet ihnen einen Vertrag an: Jeder Wunsch kann erfüllt werden, im Austausch dafür, magische Kräfte zu erhalten und eine Puella Magi zu werden – ein magisches Mädchen, das damit beauftragt ist, surreale, unsichtbare Feinde namens Hexen zu bekämpfen. Bevor sie antworten können, greift eine mysteriöse Transferstudentin namens Homura Akemi ein und versucht verzweifelt, Madoka davon abzuhalten, den Vertrag einzugehen. Madoka und Sayaka lernen dann Mami Tomoe kennen, eine freundliche ältere Schülerin, die bereits ein magisches Mädchen ist. Mami nimmt sie auf ihre Hexenjagden mit, um ihnen die Verantwortungen der Rolle zu zeigen, und Madoka beginnt ernsthaft zu erwägen, ihren Wunsch zu nutzen, um wie Mami eine Heldin zu werden.

Die Geschichte spielt in der futuristischen, fiktiven Stadt Mitakihara in Japan, einem Ort, der zunächst friedlich erscheint, aber Labyrinthe bizarrer und abstrakter Architektur verbirgt, in denen Hexen ihre Verstecke haben. Der Ton ändert sich dramatisch, als Mami während eines Kampfes von einer mächtigen Hexe getötet wird. Dieses traumatische Ereignis zerstört Madoka und Sayakas naive Sicht darauf, ein magisches Mädchen zu sein, und offenbart, dass dieses Leben voller Leid und tödlicher Gefahren ist. Ein weiteres magisches Mädchen, die aggressive und kampferprobte Kyoko Sakura, kommt in die Stadt und gerät mit Sayaka über Territorium und Ideologie in Konflikt.

Im Verlauf der Serie wird die dunkle Wahrheit hinter dem System der magischen Mädchen aufgedeckt. Sayaka, die sich wünscht, die Hände eines Jungen, den sie liebt, zu heilen, wird ein magisches Mädchen, nur um in Verzweiflung zu verfallen, als ihre Liebe nicht erwidert wird. Madoka erfährt, dass die Seele eines magischen Mädchens extrahiert wird, um einen Seelenstein zu formen, die Quelle ihrer Kraft, und dass, wenn dieser Stein vollständig von Verzweiflung befleckt wird, er sich in einen Trauersamen verwandelt, aus dem dann genau die Hexen schlüpfen, die sie bekämpfen sollen. Kyubey offenbart seine außerirdische Natur und erklärt, dass seine Rasse seit Jahrtausenden die Energie von magischen Mädchen, die sich in Hexen verwandeln, erntet, um dem Wärmetod des Universums entgegenzuwirken. Homura, das Mädchen, das versuchte, Madoka aufzuhalten, entpuppt sich als ein magisches Mädchen aus einer gescheiterten Zukunftstimeline, das denselben Monat unzählige Male durchlebt hat, in einem verzweifelten Versuch, Madoka vor einem schrecklichen Schicksal zu bewahren.

Im letzten Erzählbogen erliegt Sayaka der Verzweiflung und verwandelt sich in eine Hexe. Madoka und Kyoko versuchen, sie zu retten, aber der Plan scheitert und Kyoko opfert sich selbst. Homura bleibt allein zurück, um sich Walpurgisnacht zu stellen, einer übermächtigen „Drama“-Hexe, die als sich drehende, kopfüber hängende Figur erscheint, doch sie wird besiegt. Als Homura kurz davor steht, selbst zur Hexe zu werden, akzeptiert Madoka schließlich den Vertrag. Sie äußert einen Wunsch, der die bestehenden Regeln des Universums transzendiert: alle Hexen aus der Existenz zu löschen, bevor sie geboren werden, in Vergangenheit, Gegenwart und Zukunft. Der Wunsch verwandelt sie in ein gottähnliches, allgegenwärtiges Wesen, bekannt als das „Gesetz der Zyklen“, das persönlich jedes magische Mädchen vor der Verzweiflung rettet, bevor es zur Hexe werden kann. Die Welt wird umgeschrieben, sodass Hexen nie existiert haben. In dieser neuen Realität erinnert sich nur Homura an Madoka, die als physische Person aufgehört hat zu existieren, und Homura schwört, weiter in ihrer Ehre zu kämpfen.