El paseo toma el nombre de la ermita que el corregidor de Madrid Francisco Antonio de Salcedo y Aguirre, primer marqués de Vadillo, mandó construir a Pedro de Ribera entre 1716 y 1718 a orillas del Manzanares. La advocación —Virgen del Puerto— es la patrona de Plasencia, ciudad en la que Vadillo había sido corregidor entre 1689 y 1696, y donde desarrolló su devoción mariana. El sobrenombre «del Puerto» designa en Plasencia el paraje donde la tradición sitúa el hallazgo de la imagen: el cruce del camino viejo del puerto de Castilla, en el monte Valcorchero. La leyenda añade una capa: caballeros portugueses habrían traído la talla desde Lisboa huyendo de los musulmanes y la habrían ocultado en aquellos riscos —de ahí su apodo extremeño «la Canchalera»—. La imagen madrileña es una réplica de esa talla gótica del siglo XV.
El tramo que hoy conocemos como Paseo de la Virgen del Puerto es la primera gran obra urbana de Pedro de Ribera en Madrid. El encargo fue doble: la ermita y el arreglo del terreno entre el Campo del Moro y el río Manzanares, los llamados Campos de la Tela, donde los caballeros de los Austrias habían ejercitado sus caballos. Vadillo quería dignificar esa ribera izquierda que presentaba un aspecto selvático y, de paso, dar cobijo permanente a la copia de la Virgen placentina que ya guardaba en el Colegio Imperial de la Compañía de Jesús, en la calle Toledo.
Las obras de la ermita concluyeron en 1718. El 10 de septiembre de ese año, con presencia del Ayuntamiento y la Corte, la imagen fue trasladada en procesión desde el Colegio Imperial hasta su nueva sede barroca. El edificio es un octógono con cúpula, cuatro capillas en exedra y cuatro pilares, con fachada austera y dos torres rematadas en chapitel de pizarra —guiño a la arquitectura de los Austrias— mientras el interior despliega el programa decorativo barroco que caracterizará a Ribera en obras posteriores como el puente de Toledo y el cuartel del Conde-Duque. El mismo arquitecto talló en 1729 el sepulcro del marqués, que permanece en el interior: Vadillo murió el 24 de junio de ese año y fue enterrado junto al altar que había costeado.
El paseo arbolado se completó en 1726 y recibió el nombre de la ermita. Durante el reinado de Fernando VI se abrió el camino Alto de la Virgen del Puerto y se construyó la escalinata doble que salvaba el desnivel entre el paseo superior y la ermita. Con Carlos III, el Paseo Nuevo fue elevado y reordenado como parte del proyecto de conectar el puente de Segovia con el camino de El Pardo, para que la entrada a Madrid por la Puerta de San Vicente ganara prestancia. El arquitecto Juan Durán añadió en torno a 1780 nuevas dependencias a los edificios anejos, que servían como escuelas para los hijos de las lavanderas que trabajaban en el río.
La ermita quedó destruida durante la Guerra Civil; solo sus muros maestros y la cúpula ochavada permanecieron en pie en 1939. La talla original se perdió. La reconstrucción, a cargo del ingeniero Carlos Mendoza, fue declarada Monumento Nacional en 1945 y el culto se reanudó en 1951. Restauraciones posteriores de la Dirección General de Bellas Artes, entre los años cincuenta y ochenta, y la integración del conjunto en el proyecto Madrid Río durante el siglo XXI, completaron la recuperación del espacio.
El Paseo de la Virgen del Puerto discurre hoy por la margen izquierda del Manzanares desde el inicio del puente de Toledo hasta el puente del Rey, ya junto a la Puerta de San Vicente, en el distrito Centro, barrio de Palacio.
Las mozas madrileñas ofrecían un melón a la Virgen durante la romería del 8 de septiembre esperando encontrar novio. La costumbre dio nombre popular a la festividad: Verbena de la Melonera. Los vendedores de Villaconejos instalaban sus puestos junto a la ermita aprovechando que el lugar quedaba fuera de los portazgos de la ciudad y podían vender sin pagar los arbitrios de consumo de la villa. La tradición persistió hasta bien entrado el siglo XX; tras la destrucción de la Guerra Civil, Enrique Tierno Galván recuperó las fiestas en 1983 trasladándolas al paseo de la Chopera, en Arganzuela.