Las criaturas y tierras legendarias se introdujeron en 1994 con Leyendas, la tercera expansión del juego. Aunque algunas cartas impresas antes de Leyendas representan individuos únicos y lógicamente habrían sido legendarias, fueron y siguen siendo tratadas como no legendarias. El primer artefacto legendario, Espada de los elegidos, se imprimió en la colección Fortaleza en 1998, y los primeros encantamientos legendarios se imprimieron en Campeones de Kamigawa en 2004.
La forma en que funcionaba la regla de leyenda cuando se introdujo por primera vez difería de su forma actual: si una carta legendaria entraba en juego cuando ya había otra copia de la misma carta, la leyenda recién jugada se ponía en el cementerio, pero no la que ya estaba en juego. Esto podía suponer una ventaja significativa para el jugador que jugara la leyenda primero, y era un problema especialmente con las leyendas que podían jugarse de forma barata y rápida, como Lin Sivvi, héroe desafiante.
Al principio, las criaturas legendarias se imprimían con «Leyenda» como tipo de criatura. En aquella época, la mayoría de las criaturas que no eran artefactos (que no tenían ningún tipo de criatura) solo podían tener un tipo de criatura, así que «Leyenda» sustituía a cualquier otro tipo de criatura que pudieran tener. Más tarde, algunas leyendas se imprimieron con un texto adicional que les otorgaba tipos de criatura adicionales: por ejemplo, aunque Barrin, Maestro Hechicero tiene «Leyenda» como tipo de criatura, el texto de la carta dice «Barrin, Maestro Hechicero cuenta como Mago», otorgándole efectivamente el tipo de criatura Mago también. A partir de la colección Destino de Urza de 1999, las criaturas legendarias pasaron a tener varios tipos de criatura: por ejemplo, Rayne, Canciller de la Academia se imprime simplemente como «Leyenda de Mago», por lo que el texto «cuenta como Mago» es innecesario. El estatus de «Leyenda» como tipo de criatura podía ser explotado usando la carta Selección antinatural: un jugador podía eliminar las criaturas de un oponente cambiándolas por Leyendas, activando la regla de leyenda.
En 2004, la Leyenda fue eliminada como tipo de criatura, haciéndola inaccesible por Selección antinatural, y la regla de leyenda fue cambiada, sólo para ser activada si dos (o más) permanentes legendarios tienen el mismo nombre. Como resultado, en las siguientes colecciones se imprimieron nuevas cartas legendarias baratas. Las primeras criaturas legendarias que solo tenían «Leyenda» como tipo de criatura han sido dotadas retroactivamente de otros tipos de criatura.
En 2013, la regla de Leyenda se cambia a la forma actual, en la que el rango de influencia pasó de ser todo el campo de batalla a ser el propio jugador. Esto evita cualquier posibilidad de utilizar la regla de leyenda como medio para eliminar las cartas legendarias de los oponentes jugando otra de la misma carta legendaria o haciendo una copia de la misma.