A mediados de 1864, en la junta general de la Compañía del Ferrocarril de Medina del Campo a Zamora y Orense a Vigo se decía que cerca de cinco mil trabajadores abrían la vía, y se señalaba a marzo de 1867 como fecha de finalización del tendido férreo. No iba a ser tan fácil.
Dos años después, la compañía pedía auxilio al Gobierno porque sus acciones se habían depreciado de una forma considerable y no se alejaba la conclusión de las obras. En julio de 1871, la empresa decía que los retrasos se estaban acumulando en los numerosos túneles, puentes y el viaducto de Redondela, la obra más notable. Comunicaba, a sus accionistas que 100 de los 132 kilómetros del recorrido quedarían concluidos a finales de ese mismo año.
Los problemas financieros paralizaron las obras a finales de 1873. Solo una ampliación de capital permitió, junto a una nueva prorroga de la concesión, reiniciar las obras. En junio de 1876 se inauguraba el viaducto de Redondela; en agosto de 1877, Alfonso XII, inauguraba el tramo Redondela-Vigo. Así hasta el 9 de junio de 1881, cuando fue abierta la línea entre Vigo y Ourense. Curiosamente, al día siguiente se produjo el primer atropello con fallecimiento de una personas, al parecer sorda, en un punto cercano a Redondela. El 18 de junio de 1881 salía de Vigo el primer tren de viajeros, acomodados en tres vagones a techo descubierto. Dos días más tarde se producía el primer descarrilamiento del tren correo. El 25 de marzo de 1886 se inauguraba el puente internacional de Tui.