Verlaine voltou a Paris em agosto de 1871 e, em setembro, recebeu a primeira carta do poeta Arthur Rimbaud. Em 1872, ele já havia perdido interesse em Mathilde, e logo abandonou-a com seu filho, preferindo a companhia de seu novo amigo. A tempestuosa relação entre Rimbaud e Verlaine os levou a Londres, em 1872. Em julho de 1872 em uma crise de desespero Verlaine disparou dois tiros com uma pistola em Rimbaud, atingindo seu pulso, mas sem causar-lhe sérios danos. Como resultado indireto desse acidente, Verlaine foi preso e encarcerado em Mons, onde ele experimentou uma conversão à Igreja Católica, o que novamente influenciou suas obras e provocou críticas afiadas de Rimbaud. "Romances sans paroles" foi o resultado poético deste período. Depois de sair da prisão, Verlaine viajou novamente à Inglaterra, onde trabalhou por alguns anos como professor e produziu outra obra de sucesso, Sagesse. Ele voltou à França em 1877 e, enquanto ensinava Inglês em uma escola em Rethel, apaixonou-se por um de seus alunos, Lucien Létinois, que foi quem o inspirou a escrever seus próximos poemas. Verlaine ficou devastado quando o garoto morreu de tifo em 1883.
Os últimos anos de Verlaine testemunharam dependência de drogas, alcoolismo e pobreza. Ele viveu em bairros pobres e hospitais públicos, e passava seus dias bebendo absinto em cafés parisienses. Por sorte, o amor à arte dos franceses foi capaz de dar-lhe apoio e alguma ajuda financeira: suas poesias antigas foram redescobertas, seu estilo de vida e estranho comportamento em frente a plateias atraíram admiração, e em 1894 ele foi eleito "Príncipe dos Poetas" da França. Sua poesia foi admirada e reconhecida como inovadora, servindo de fonte de inspiração para famosos compositores, como Gabriel Fauré, que transformou vários de seus poemas em música, incluindo La bonne chanson, e Claude Debussy, que tornou música cinco dos poemas de Fêtes galantes. Paul Verlaine morreu em Paris com 52 anos de idade, em 8 de janeiro de 1896, e foi enterrado no Cimetière des Batignolles.