A ligar a Avenida João XXI à Avenida de Madrid encontramos hoje a Rua Cervantes, atribuída em 1948, hoje paralela ao Autoparque Madrid, um topónimo de 2001.
A Rua Cervantes resultou da publicação do Edital municipal de 29 de julho de 1948, fixada no arruamento identificado então como Rua D2 da Zona compreendida entre a Alameda Dom Afonso Henriques e a Linha Férrea de Cintura. Este Edital resultou da procura da edilidade lisboeta de imprimir algum cosmopolitismo à cidade, com doze topónimos, todos ligados a personalidades de cariz internacional ou a cidades europeias e brasileiras, onde couberam os nomes dos cientistas europeus Pasteur e Marconi, do inventor americano Edison, dos escritores Vítor Hugo (francês), Afrânio Peixoto e João do Rio (brasileiros), bem como Avenidas para Madrid, Paris e Rio de Janeiro, uma praça para Londres, para além da Avenida João XXI que homenageia o único Papa português.
O castelhano Miguel de Cervantes Saavedra (Alcalá de Henares/29(?).09.1547 – 22 ou 23 (?).04.1616/Madrid) foi um romancista, dramaturgo, poeta, soldado e cobrador de impostos, autor do famoso D. Quixote de la Mancha, considerado o primeiro romance moderno, que teve licença de impressão em 26 de setembro de 1604 e alcançou um êxito enorme com 9 edições em 1605: duas em Madrid, três em Lisboa (sem o consentimento do autor) e duas em Valência.
Cervantes enquanto soldado, lutou em Itália (1569), combateu na Batalha de Lepanto (1571), nas Jornadas de Tunes e da Goleta (1573), foi feito cativo por corsários em Argel (1575 – 1580), onde conheceu Manuel de Sousa Coutinho (Frei Luís de Sousa), de quem aliás narrou os amores em Trabajos de Pérsiles y Sesinanda (1616). Regressado a Espanha passou a ser cobrador de impostos e veio para Portugal em 1581 para conseguir entrar na corte de Filipe II de Espanha e I de Portugal, tendo ficado em Lisboa até 1583 e escrito a ideia «Para festas Milão, para amores Lusitânia».
Em 2001, pelo Edital municipal de 3 de janeiro, o espaço compreendido entre a Avenida de Madrid, Rua Cervantes e Avenida João XXI passou a denominar-se Autoparque Madrid, referindo-se o topónimo à artéria onde se abre o Autoparque, uma nova categoria de via pública essencialmente destinada ao parqueamento automóvel cuja denominação corresponde sempre ao nome da artéria que lhe dá acesso.