En 1876 con motivo de la construcción de la línea ferroviaria entre Salto y Artigas, es creada en Londres la Compañía North Western Railway of Montevideo, quien iniciaría la construcción de dicho ramal ferroviario, pero debido a problemas financieros se vio obligada a ir a la quiebra.
En 1882 los antiguos inversores de la ya desaparecida Compañía North Western Railway of Montevideo, deciden fundar la ahora llamada North Western Railway Uruguay quien retomaría la construcción del ya mencionado trazado.
El trazado, circularía por Palomas y Baltasar Brum, donde se realizaría la conexión con el Ferrocarril del Norte de Uruguay hasta llegar a a Bella Unión, donde se construyó en 1887 la Estación Cuareim, muy cercana al río homónimo, división natural de la frontera con Brasil.
En 1897 sería construido el puente ferroviario y se lograría la conexión internacional con la ciudad de Barra do Quaraí, como también permitiendo las conexiones con hacia Uruguaiana y otros puntos del sur de Brasil.
En enero de 1939 comenzó a operar el servicio Bella Unión - Montevideo.