Sortie en Mars 1998, Cette extension comportait 143 cartes (44 Rares, 44 Uncos, 55 communes). Imprimées à 180 Millions d'exemplaires en Bord Noir et symbolisée par un portail. Forteresse était vendue en boosters de 15 cartes (1 Rare, 3 Uncos, 8 communes).
Les Cartes Connues sont Mox de diamant, Reine des slivoïdes, Maniaque mogg
La 13ème extension de Magic s'inscrit dans la lignée de Tempête, reprenant et développant les mêmes concepts. Les slivoïdes, qui jusque la n'étaient pas joués ont trouvé avec cette extension, de bonnes raisons que l'on s'intéresse à eux. Tous les slivoïdes de Forteresse sont bicolores, et 2 d'entre eux sont particulièrement puissants : le bleu/blanc rend tous les slivoïdes inciblables, et le rouge noir permet de sacrifier 1 slivoïde pour infliger 2 blessures à une cible. La reine des slivoïdes, 7/7 pour 1 mana de chaque couleur et permettant de créer des jetons slivoïdes à également encouragé les joueurs à créer des decks de ce type.
Forteresse ajoute également 2 nouveaux types de créatures. Les en-Kor ont la capacité de rediriger les dommages qui leurs sont infligés. Les épix sont des créatures 0/0 qui arrivent en jeu avec un certain nombre de marqueurs +1/+1, qui peuvent être retirées pour produire un effet. Les murs de l'extension Forteresse ont également eu un impact important sur les jeux de tournois, et en particulier le mur de fleurs, qui permet de piocher une carte quand il arrive en jeu, souvent combiné avec le chevaucheur des alizés qui permet de le remonter en main.