Publicado
el 25 de Agosto de 1986 en tres formatos. LP, Casete, Compac Disc (CD) y Cartucho de 8 Pistas (8 Tracks).
Ediciones Chilena, Turca y Sudafricana
Ediciones de Argentina y México (Centro y derecha) con titulo de canciones en español
Ediciones de Japón, Venezuela y Uruguay
Hungria, USA(Club Edition), Nueva Zelanda
Filipinas, Indonesia, Colombia
Aunque ya en deshuso en aquellos tiempos, Graceland llegó a ser editado en una tirada muy reducida en Cartucho de 8 pistas (8-Track). Fabricado por Columbia House bajo licencia de Warner, a día de hoy conseguir una copia es muy difícil.
Como curiosidad tenemos la versión del LP lanzada en Sudáfrica, Australia y Turquía con las fotos intercambiadas. Algo que también ocurría en la versión Mexicana del LP que además venía con un rotulo que anunciaba "Puedes llamarme Al".
Abajo a la derecha, edición Argentina con los titulos de canciones y el texto de la contra traducidos al español.
A principio de los 90 Warner lanza la discografía de Simon en un nuevo formato de empaquetado alargado llamado "Longbox" (según cuentan, para aprovechar los contenedores de los discos vinilo de las tiendas, ya en desuso en esas fechas). No tiene mucha aceptación y en 1993 se deja de fabricar, volviendo a la caja cuadrada que ha perdurado hasta ahora. Los Longbox ahora se consideran objetos de coleccionistas.
A principio de los años 90 se editó en un nuevo soporte,
el casete compacto digital, o Digital Compact Cassette en inglés (DCC), fue un formato de cinta magnética de audio, de casete compacto, con base de óxido de cromo, que se utiliza como soporte para la grabación magnética digital y en la reproducción de sonido presentado por las empresas Philips y Matsushita al final de 1992 y comercializado como el sucesor del casete analógico convencional. Fue también competidor del formato MiniDisc de Sony. Philips no logró su objetivo y el DCC fue un formato efímero. Sus inconvenientes pesaron más que sus ventajas y el formato fue un fracaso, siendo retirado del mercado en 1996.
En 1996, para celebrar el 10º aniversario de su publicación, Warner. Como novedad incluía una pista para reproducir en el ordenador con videos, imágenes y entrevistas. Es conocido como Graceland Enhanced.
Hasta julio de 2004 no es reeditado de nuevo, con sonido remasterizado y con 3 temas extras:- Homeless (demo)
- Diamonds On The Soles of Her Shoes (versión inédita)
- All Around The World (1ª version)
En 2010. Con Paul Simon fuera de Warner Bros Records, mueve todo su catálogo en solitario a Legacy Recordings, una división de Sony Music Entertainment, cumpliendo así su deseo de que su catálogo tanto con Simon & Garfunkel como en solitario permanezcan unidos. Una especie de vuelta a los origines ya que Columbia / CBS fue adquirida por Sony Music.
Legagy Recordings vuelve a sacar en cd los mismos títulos remasterizados editados por Warner en 2004, tal cual, con los mismos bonus tracks. Las ediciones solo se distinguen por el cambio de logo de las compañías.
Ese mismo año, 2011, Sony edita en Japón la discografía de Paul Simon en funda de carton imitando al LP original en formato Blu-Spec CD.
Sistema basado en la tecnologia Blu-Ray, se trata de una aplicación del proceso de grabación a través de láser azul que permite una mayor precisión y, por tanto, una mayor fidelidad de sonido gracias a la reducción de posibles errores de lectura.
En 2012 para celebrar el 25 aniversario del disco, Legacy vuelve a editar el disco, en LP y en CD, este con los mismos tres temas extras que la edición de 2004 y la inclusión de la pista "The Story of "Graceland" donde de la voz del propio Paul Simon nos cuenta la historia de Graceland.
También se puso a la venta una edición (en formato digipack y en carcasa de plástico) que además incluía el DVD con el documental "Under African Skies".
A su vez se editó una caja deluxe donde se incluía un CD solo para el material extra donde se añaden los tres temas mencionados antes de la edición de 2004 más dos demos grabadas en los Ovation Studios de Sudafrica: "You Can Call Me Al (demo)" y "Crazy Love (demo)" .
Además de los Cds se incluían los dvd de "Graceland: The African Concert" y del documental elaborado para la ocasión "Under African Skies", un poster, un libro y una reprodución del cuaderno con las letras manuscritas de Paul Simon.
En Japón también salió a la venta en formato "Blu-Spec CD2" o BSCD2. Un formato mejorado del "Blu-Spec" que te comentábamos más arriba.
En agosto de 2015 Newbury Comics pone a la venta una edición exclusiva de 2000 copias del vinilo en color marron. 
En febrero de 2019 salió una edición exclusiva de solo 50 ejemplares con el vinilo en color azul.
Formaba parte de la serie Unicef Blue Vinyl, 17 álbumes clásicos y contemporáneos prensados en color azul creados para recaudar fondos y crear conciencia sobre la Children's Emergency Fund. Limitados a solo 50 copias, todas numeradas individualmente y con un holograma de Unicef.
Solo se podían conseguir mendiante sorteo donando dinero en una web creada para la ocasión.
En octubre de 2020 con motivo del National Album Day, se puso a la venta en Reino Unido una edición limitada con el vinilo trasparente.
