El origen del barrio se remonta al poblado Victoria, fundado el 12 de septiembre de 1842 y nombrado en honor a la reina Victoria del Reino Unido,[1] área que comprendida por 122 manzanas pertenecientes al empresario anglouruguayoSamuel Lafone y delineadas por dos agrimensores de la Comisión Topográfica: Gutiérrez y Eguía. En dichas tierras, anteriormente se ubicaba la estancia jesuíta Jesús María. En 1841, Lafone había establecido un saladero sobre la costa de la Bahía de Montevideo y la desembocadura del arroyo Pantanoso, en un paraje denominado Rincón de La Teja.[2]
Los primeros habitantes fueron inmigrantes españoles, vascos, franceses e italianos, que se se desempeñaban como obreros o trabajadores del saladero, sin perjuicio de que fuentes de trabajo fueron proporcionadas por el embarcadero establecido por Antonio Lussich y el peladero de cueros y mataderos.[3] En un inicio, el pueblo era reconocido por las construcciones de las viviendas con techo a dos aguas. A poco de fundarse el barrio, ya se habían construido cuatro edificios y se había proyectado la construcción de dos puentes: uno sobre el arroyo Miguelete, y el otro sobre el arroyo Pantanoso.[4]
En el año 1869 llegó a Paso Molino el primer tranvía de caballos. Esta novedad, acerca un medio de transporte a los escasos pobladores del lugar.[5] A principios del siglo XX se convierte en una gran zona comercial e industrial, con la instalación de frigoríficos.[6] Los terrenos que ocupaba el saladero de Lafone fueron adquiridos en 1914 por el Estado uruguayo, y en su lugar se construyó la planta de refinación de petróleo de la empresa estatal, ANCAP.[7]