The Magic: The Gathering storyline is convoluted, hard to find in one place, and contains many less-than-relevant plot details. Here, I will attempt to gather only the most meaningful places, events, and people. If you have no idea where to start with Magic lore, this is your entry point.
Our story begins on the plane of Dominaria. Long before the five colors of Magic were mastered, a civilization known as the Thran Empire made powerful artifacts fueled by magical battery-rocks called Powerstones. This was well and good until it was discovered that these Powerstones were giving people diseases; to combat this, the Thran leaders called in a disease specialist named Yawgmoth. Yawgmoth had a bit of a sketchy reputation, and had been exiled once before, but he cured the disease and rose to great power in doing so. Unfortunately for him, it was soon discovered that during his exile, he committed horrific acts in the name of studying disease. A civil war broke out between Yawgmoth’s supporters and the people who knew the truth about him, and Yawgmoth realized his time with the Thran was nearing its end.
Yawgmoth saw an opportunity when a Planeswalker named Dyfed visited the Thran Empire. Planeswalkers, as you may or may not know, are individuals of immense magical power and talent who have the ability to travel between planes at will. Yawgmoth tricked Dyfed and convinced her to find him a new plane to call home. Dyfed found Phyrexia, a metal world of nine nested spheres abandoned by its original creator. She constructed a portal there and brought Yawgmoth, who populated it with his own followers and began using his background in genetic manipulation to reshape the plane to his vision.
Eventually Dyfed realized Yawgmoth was up to no good, but the damage was done; Yawgmoth had bound himself to the core of the plane. He had essentially become a god, Phyrexia had become Machine Undeath Hell World, and his followers had become horrific mutated amalgamations of twisted metal and decaying flesh. Yawgmoth began his campaign to crush the Thran, and was horribly successful. The Thran were able to seal the Phyrexian portal with a Powerstone, but their civilization was already doomed to extinction. The Thran died out, but Dominaria was safe from the Phyrexian threat… for now.
The Phyrexian portal laid undiscovered for eons until it was found by two archaeologist brothers, Urza and Mishra. They removed the portal’s Powerstone, breaking it in half and each keeping one piece for themselves. This began the Brothers’ War, in which both Urza and Mishra gathered huge armies and constructed deadly artifacts in a bloody struggle for both halves of the stone. Further complicating matters was the Phyrexian officer Gix, who became aware that the portal was once again active and used it to infiltrate both sides of the war.
Eventually, there came a final climactic battle between the two brothers. Urza injured Mishra during this battle, and in his wound Urza saw that Mishra had replaced parts of his body with machinery, like the Phyrexian infiltrators. He blamed the Phyrexians for the tragic war against his brother and flew into a rage, activating an artifact of immense power and destroying both his and his brother’s armies. The explosion disabled the Phyrexian portal and caused Urza to ascend, becoming a planeswalker with his eyes replaced by the two halves of the Powerstone.
Urza left the plane of Dominaria and began his millennia-long preparation for his war against the Phyrexians. He developed the Legacy Weapon, a device powered by several powerful artifacts including the Powerstone, a silver golem named Karn, and Gerrard Capashen, a human heir Urza engineered with a multi-generational breeding project. Meanwhile, Yawgmoth had started loading his armies onto an artificial plane called Rath, with the intention of merging the plane with Dominaria and therefore bringing his entire force there at once.
After lifetimes of planning, the Phyrexian Invasion began. Yawgmoth overlaid Rath onto Dominaria, and the full extent of the Phyrexian horror arrived on the plane. Urza and Gerrard were eventually captured by the Phyrexians and forced to fight each other in arena combat, during which Gerrard decapitated Urza. Gerrard escaped Phyrexia with Urza’s head and reunited with Karn, shoving Urza’s Powerstone eyes into Karn’s chest and completing the Legacy Weapon. The blast destroyed Yawgmoth, consumed Gerrard, ended the war, and caused Karn to gain the powers of a Planeswalker. Dominaria was ravaged, but once again safe from Phyrexia.
Devastated after the horrors he had witnessed during the war, Karn used his newfound Planeswalker powers to create a plane of his own vision: Argentum, a world made entirely of metal. The depressed Karn lingered on his plane in a self-imposed exile, but still sent out probes to keep tabs on Dominaria. One probe, however, was flawed, and became the Mirari, a magical orb with the ability to grant the deepest desires of its user. To make a long story short, the Mirari was not good for Dominaria and led to the creation of a demigod and yet another continent-engulfing apocalypse.
When Karn became aware of this, he returned to Dominaria to retrieve his creation. He brought the Mirari to Argentum and gifted it to his most trusted golem. Tasking the golem with protecting the plane Karn had created, Karn set out to explore the Multiverse. Meanwhile, the golem slowly became corrupted by the Mirari and traces of Phyrexian oil Karn had unknowingly brought with him to Argentum. He went insane and reshaped the world according to his vision, naming it Mirrodin and himself Memnarch. Karn had to come back and undo the damage he caused (again), destroying Memnarch and recovering the Mirari.
It was about this point that Dominaria was starting to feel the strain from all the cataclysms that had happened there over the millennia. Rifts in time and space started appearing, causing strange disturbances throughout the plane. Karn teamed up with a bunch of other Planeswalkers to mend the rifts, each of them giving up their Planeswalker powers to seal the rifts in an event known as the Mending.
With the last of his Planeswalker powers, Karn flung himself back to Mirrodin, but he did not like what he had found. The same Phyrexian oil that had taken control of Memnarch was seeping into the rest of the plane, and a new Phyrexian menace was beginning to emerge. These Phyrexians trapped Karn in the core of the plane, declaring him the Father of Machines and tormenting his mind with their demented whispers. On the surface, a war was beginning to break out between the citizens of Mirrodin and these twisted abominations that had appeared.
Mirrodin, being made entirely of metal, was a fantastic breeding ground for the Phyrexians, and they were winning the war. A Mirran Planeswalker named Koth recruited two other planeswalkers, Elspeth Tirel and Venser, to help him fight the war. Elspeth was a valorous knight who had faced the Phyrexians before on her home plane, and Venser was an artificer who had helped Karn seal the portals during the Mending. The three journeyed to the center of Mirrodin in search of Karn, and found him driven nearly insane by the Phyrexians. Venser nobly sacrificed his life to transfer his Planeswalker powers to Karn, purifying him of the Phyrexian corruption and restoring him to Planeswalker status.
But, once again, the damage was done. Koth, Karn, and Elspeth returned to the surface to find Phyrexia had overrun the plane, turned almost every being into their corrupted vision of life, and declared Mirrodin was now New Phyrexia. Devastated by guilt, overwhelmed with fear, and weary from battle, Karn and Elspeth fled the plane to recover and gather support for yet another Phyrexian war. Koth remained, and continues to fight for his home world to this day.
Before the Mending, Planeswalkers were essentially gods. They lived forever, could change their appearance at will, and had near-limitless powers. The Mending took away the majority of that power, leaving Planeswalkers the ability to travel from plane to plane at will but otherwise making them no more than very talented wizards.
Nicol Bolas, a dragon Planeswalker who had lived an exceptionally long time, was not pleased at this development, and dedicated himself to doing whatever it took to restore his former powers. Being an ancient dragon of unmatched power, patience, and intelligence, his plans were intricate, manipulative, and eon-spanning. The most devastating of these plans was the release of the three Eldrazi titans.
Many millennia ago, the titans Emrakul, Kozilek, and Ulamog roamed the Multiverse, all-powerful and ever-hungry. They would manifest on a plane, devour its energy and inhabitants, and promptly leave for the next one. The spirit dragon Planeswalker Ugin recognized their threat to the Multiverse and, fearing they couldn’t (or shouldn’t?) be killed, decided to trap them to one plane, endangering the plane but sparing the Multiverse. With the help of two other Planeswalkers, the vampire Sorin Markov and the lithomancer Nahiri, Ugin rendered the Eldrazi inert and bound them to the plane of Zendikar, where they would stay for 6000 years and eventually be forgotten.
But Bolas did not forget. For reasons currently unknown but undoubtedly sinister, he tricked three other Planeswalkers into releasing the seal on Zendikar. The Eldrazi were freed, and posed a threat to the Multiverse once again. Emrakul gathered enough strength to abandon Zendikar after a short while, but Ulamog and Kozilek stayed to consume and ravage the plane.
The Planeswalker Gideon Jura was on the plane when the titans were released. After nearly losing his life fighting them, he planeswalked away, intending to seek help from other Planeswalkers and return to put a stop to the Eldrazi menace. He recruited a team of Planeswalkers to help him: Jace Beleren, a mind mage; Chandra Nalaar, a pyromancer; and Nissa Revane, a nature mage. Jace, Chandra, and Nissa all had a personal stake in this battle; Jace and Chandra were two of the Planeswalkers manipulated into opening the seal, and Zendikar was Nissa’s home plane. Together, and through much hardship, they actually managed to kill both Ulamog and Kozilek before Zendikar was completely destroyed.
Having witnessed the incredible damage done to the plane, the four Planeswalkers agreed that with their power, they had a responsibility to prevent events like this from happening to other planes. They formed a team and dubbed themselves The Gatewatch. Their first order of business was to find Emrakul, the missing third Eldrazi titan. Jace left Zendikar to seek out Sorin Markov on his home plane of Innistrad, hoping that he would have some answers. But Jace didn’t even have to find Sorin to get his answer; a centuries-old feud between Sorin and Nahiri had caused the lithomancer to summon Emrakul directly to Innistrad.
Jace called the rest of the Gatewatch to Innistrad and they attempted to defeat Emrakul as they did the previous two Titans, but Emrakul was much more powerful than Ulamog and Kozilek were. Even with the help of the necromancer Planeswalker Liliana Vess, the newest addition to the Gatewatch, the battle was looking hopeless. The plane was only saved by the help of the lunar sage Planeswalker Tamiyo, who helped the Gatewatch seal Emrakul away in Innistrad’s moon. But the victory was not a true one; Emrakul, sensing Innistrad’s resistance to her, had sealed herself in the moon by taking control of Tamiyo, promising to return when Innistrad was ready to accept her. Creepy!
This brings us to the present day in the Magic storyline, with New Phyrexia and Nicol Bolas still presenting ever-increasing threats to the Multiverse, and Emrakul’s return looming over Innistrad’s horizon. Congratulations! You’re caught up. If you want to read more, I recommend skimming through the pages of the MtG Salvation Wiki. You can also get a “where are they now?” of current Planeswalkers on the official Wizards of the Coast website, as well as all of the official Magic stories sorted by plane.
Unfortunately, it's a year or two out of date.