Se encuentra esta calle en un sector del Ensanche que, según el plan inicial de Carlos María de Castro, sería militar, pues en él se instalarían varios cuarteles, cárceles y un campo de Marte como el que tiene París ante la torre Eiffel. Sin embargo la idea no se cumplió y ésta es hoy en día una calle en la que vive primordialmente la clase media tirando hacia media-alta. Pero no siempre fue así; el barrio no se urbanizó hasta bien entrado el siglo XX. Répide aún comenta que la calle tiene escasas edificaciones y que atraviesa el cerro del Pimiento, que todavía tardaría mucho en ser engullido por el hormigón y el asfalto. Precisamente donde hoy termina esta calle se hallaba el hospital de epidemias del cerro del Pimiento. Empezó a construirse este centro en 1885, tras una de las diversas epidemias de cólera que en aquella época sufrieron la villa de Madrid y otros puntos de España. Se detuvieron las obras, pero en 1895 se volvió sobre ellas y se terminó, en previsión de un posible brote de Yersinia pestis, el bacilo de la peste. Aun acabado el hospital, se mostró inadecuado desde el primer momento por su mala ventilación y lo aislado que se encontraba, entre desmontes y caminos. Aunque se prolongó la calle de Gaztambide y se abrió el paseo de San Bernardino (actual calle de Isaac Peral) para mejorar los accesos, el centro sanitario tuvo una corta vida, pues desapareció en 1905. Su solar está hoy ocupado por el paseo de San Francisco de Sales y por edificios de viviendas.
El primer nombre que se dio a esta calle fue el de Tarifa, pero un acuerdo municipal de 29 de diciembre de 1893 la dedicó a Andrés Mellado y Fernández. Nacido en Málaga en 1846, estudió Derecho y Filosofía, pero su verdadera vocación fue la de periodista, y tan pronto como en 1868 fundó el periódico El amigo del pueblo, que difundió ideas revolucionarias e impulsó a Andrés Mellado a entrar en política. Apoyó a Salmerón y Castelar y fue ardiente partidario de la I República, durante la que dirigió otro diario, La igualdad, fundado por Estanislao Figueras y clausurado por orden de Cánovas en 1875. Pero eso no calló al inquieto periodista, que inmediatamente pasó a tomar la batuta de El imparcial, que no abandonó en diez años. En 1889 es nombrado alcalde de Madrid y en su breve mandato consiguió sanear las siempre exhaustas arcas municipales. Además fue diputado por Puerto Rico, por Málaga y por Gaucín, y senador por Cuba. Desempeñó los puestos de vicepresidente del Congreso, gobernador del Banco de España, ministro de Instrucción Pública y comisario regio del Canal de Isabel II. También fue académico de la lengua. Fue a morir muy lejos de Madrid, en Biarritz, el año 1913.
