Al mismo tiempo fue un éxito de ventas con más de 8 millones de ejemplares vendidos en todo el mundo. En octubre el sencillo "You Can Call Me Al" logra subir hasta el puesto 4 y se promociona con un original videoclip en el que interviene Chevy Chase. Sin embargo la ANC y la ONU declaran a Simon persona non grata y lo incluyen en sus listas negras por haber roto el boicot impuesto a Sudáfrica al emplear músicos de esta nacionalidad en el álbum y haber grabado parte del mismo allí. Finalmente ambas organizaciones comprendieron que el castigo al régimen del apartheid no debía suponer una penalidad añadida a su víctima, la población negra, y que Simon lo que había hecho era promocionar la cultura de color sudafricana y darle la oportunidad a no pocos de sus intérpretes de ser mundialmente conocidos y valorados, por lo que en enero de 1987 Paul dio una conferencia de prensa en Londres en la que pudo anunciar que dichas entidades lo habían borrado de tales listas negras. En febrero de 1987 comienza en Rotterdam el Graceland Tour auténtico fenómeno de masas universal que llevaría a Simon a recorrer durante dos años todo el mundo.
En la ceremonia de los premios Grammy de ese año, “Graceland” obtiene el galardón de “Disco del Año”. En septiembre de 1990 vio la luz el álbum “The Rythm Of The Saints”, en el que Simon sigue explorando la música étnica, en esta ocasión de Camerún y Brasil, e incorporándola al acervo pop americano; si algo caracterizan a este disco son las percusiones y las letras crípticas. Al igual que en 'Graceland' músicos de diversos países colaboran en este LP, como Olodum, Milton Nascimento o Vincent Nguini. El disco fue un éxito con más de 4 millones de copias vendidas en todo el mundo. Paul Simon esta de moda. El 2 de enero de 1991 se inicia en Tacoma el “Born At The Right Time Tour”, gigantesco tour promocional del disco que llevaría a Simon a recorrer todo el mundo. El 15 de agosto se celebró un multitudinario concierto en Central Park, realmente histórico, al que acudieron cerca de 1 millón de personas y que más tarde sería editado en forma de disco y de vídeo. El 30 de mayo de 1992 Paul se casó en Montauk, NY, con la cantante Edie Brickell (líder del grupo New Bohemians), 24 años más joven que Simon. Con ella nuestro artista parece haber encontrado el equilibrio y la serenidad, habiendo tenido hasta la fecha tres hijos fruto de este matrimonio.
A partir de entonces Paul Simon se dedicaría en cuerpo y alma a su siguiente proyecto, un musical para Broadway, "The Capeman '. El musical está basado en la vida de Salvador Agrón, un puertorriqueño de infancia difícil y juventud marginal que a los 16 años fue sentenciado a muerte tras haber asesinado a dos chicos blancos a los que confundió con miembros de una banda rival. Un selecto ramillete de canciones de este musical fue escogido por Simon para ser grabado e interpretado por él mismo y lanzado en forma de un nuevo CD del autor en 1997 bajo el título de 'Songs From The Capeman', en un intento de promocionar a la obra de Broadway. El resultado no fue bueno. Las mismas consideraciones que incidieron sobre la obra teatral, lo hicieron negativamente en la difusión de este disco, por otra parte muy bien acogido por la crítica. Con pérdidas finales de más de 11 millones de dólares, que ocasionaron su prematura clausura el 28 de marzo de 1998, tras apenas 68 representaciones. Los principales papeles estuvieron a cargo de los actores cantantes Marc Anthony (Salvador Agrón de joven), Rubén Blades (Salvador Agrón adulto) y Ednita Nazario (Esmeralda Agrón), todos los cuales tuvieron unas actuaciones francamente memorables.
En un intento de lavar su imagen, recuperar parte del dinero perdido en “The Capeman” y pulsar su grado de aceptación entre el público inicia en junio de 1999 una gira veraniega con Bob Dylan con la que recorre todo el país. El éxito es tal que, al finalizar en julio el tour, se ven obligados, ante la demanda a ampliarlo con varias actuaciones en septiembre, siendo la gira estival de más éxito en EEUU este año. En 2000 publicó el 'You're the one' una auténtica nueva obra maestra que devolvió de nuevo al sitio donde se merece estar Paul Simon, ese sitio junto a los mejores compositores de la historia. El álbum fue nominado a los grammys como mejor disco del año, que promocionó con una serie de conciertos por todo el mundo. El concierto de París está disponible en DVD. En el 2002 escribe una canción para la película de animación "The Wild Thornberrys" con el título de "Father and Daughter" que fue nominada al Oscar. Ese mismo año emprende gira europea. Tras la gira que le reunió con su viejo colega Art Garfunkel y que le tuvo ocupado buena parte de 2003 y 2004, vuelve al estudio de grabación y en mayo de 2006 publica un nuevo álbum de estudio "Surprise", una nueva demostración de innovacion por parte del cantante, esta vez contó con la colaboración de Brian Eno que le proporciono al disco un "Paisaje sónico" de lo más vanguardista.