Edificado sobre 14.000 metros cuadrados de marismas, en el denominado Campo del Faraón, se empezaron los trabajos de terraplenado el 12 de Septiembre de 1.890 siendo alcalde, José Cueto. El parque del Muelle fue uno de los espacios ganados para la ciudad a finales del siglo XIX, lo que hizo desplazar el puerto medieval (situado a la altura de la Iglesia de los Padres Franciscanos) hacia lo que es hoy la ría y el puerto comercial de Avilés.

Fue el parque tradicional de Aviles (y uno de los símbolos del crecimiento avilesino entre los siglos XIX y XX), desde principios del siglo XX hasta la década de los setenta, cuando entró en servicio el Parque de Ferrera. En él, tenían lugar los domingos y festivos al mediodía, conciertos de la banda municipal, apiñándose la gente en torno al magnífico templete musical (diseño de Federico Ureña), una verdadera joya en su género en Asturias.

De 14.000 metros cuadrados y diseño del arquitecto Bausá, el elegante parque del Muelle, de trazo rectangular, tiene unos cuidados jardines y unos bellos soportales vegetales. Lo que termina de singularizarlo son las 10 estatuas de hierro fundido, aquí levantadas y que fueron adquiridas en el siglo XIX por el ayuntamiento avilesino en Barcelona, aunque el molde y la realización se efectuaron en París. A estas 10, hay que unir otras 9 (aunque haya una que se repite) y que representa motivos alegóricos de la mitología griega, una de las cuales se encuentra colocada en la Fuente de la Glorieta (también conocida como Fuente de Verano) a la entrada del parque y el resto repartidos por el mismo (Náyade, Diosa Artemis, Alegoría del Verano, Alegoría del Invierno, Alegoría del Otoño, Alegoría de la Primavera, Afrodita y el Joven Sátiro). A todas estas figuras se suma un pequeño y gracioso elefante que arroja agua por su trompa.

Finalmente y en el extremo opuesto a la fuente de entrada (al fondo del salón central, parte norte), se levanta el conjunto escultórico dedicado al almirante Pedro Menéndez de Avilés “El adelantado de la Florida”. Su primera piedra se bendijo el 17 de Junio de 1.917 y se descubrió la estatua por la Infanta Isabel de Borbón el 23 de Agosto de 1.918.

En 1.925 se hicieron algunas reformas en el Parque, trasladando alguna de las estatuas a distintos sitios del jardín, emplazando dos de ellas a la subida del kiosco.

En 1.956, se colocó la Estatua de la foca como recuerdo de una que había llegado, desnortada, al puerto de Avilés a principios de aquella década. En tiempos, a su vera, se colocó una foca pequeña, cosa que no pasó de ser una broma, aunque algún desaprensivo hizo desaparecer la misma. La arribada de la foca y su popularidad coincidieron, en el tiempo, con el inicio de las obras de la enorme factoría siderúrgica Ensidesa. Asunto que algunos tomaron como un símbolo precursor de aquel gigantesco advenimiento industrial.