Il 16 Dicembre 1876, con il completamento della tratta Spina-Passofonduto, si concludevano i lavori sull’intera direttrice Palermo-Porto Empedocle, aprendo ai prodotti agricoli e minerari lo sbocco verso il mare Tirreno oppure verso quello Mediterraneo. Nello stesso anno, terminavano anche i lavori sulla direttrice Bicocca-Santa Caterina (odierna Caltanissetta-Xirbi)-Licata, consentendo di collegare il “Nisseno” con le tratte già operative che da Messina conducevano a Catania e Siracusa.
Mancava, ancora, la linea "Centrale" diretta Palermo-Catania e la scelta del tracciato che la completasse.
Ogni proposta di soluzione portò ad accese discussioni e a rissose, a volte volgari, polemiche che coinvolsero per anni politici di ogni sorta, i quali, spinti da meri scopi elettorali, assunsero i ruoli di paladini delle rivendicazioni, per lo più ridicole ed irrazionali, di alcuni comuni o di certe esigenze interprovinciali.
Alla fine, nel 1877, il tracciato per “Vallelunga” risultò essere la soluzione tecnica-politica del problema e la stazione di Roccapalumba-Alia il nodo di collegamento tra la direttrice Palermo-Porto Empedocle e la nuova linea che, attraverso le fermate di Marcatobianco e di Mimiani-S. Cataldo  e le stazioni di Valledolmo, Vallelunga, Villalba e  Marianopoli, raggiungeva la ferrovia Catania-Licata nella stazione di Santa Caterina. La costruzione della linea venne suddivisa in quattro tronchi, ciascuno dei quali dato in appalto. 

Le Imprese Appaltatrici e le lunghezze dei relativi tronchi

I lavori furono conclusi nel Dicembre 1881, eccetto per la grande galleria di Marianopoli, aperta all'esercizio il 1° Agosto 1885.

Date di apertura delle tratte della linea di Vallelunga
 

Nel periodo 1882-1885 la linea venne utilizzata costruendo un'apposita strada ed attivando un servizio di diligenza tra la fermata provvisoria di Mimiani-San Cataldo e la stazione di Marianopoli.

Orario di servizio dei treni del 15/09/1884. In esso è evidenziato il servizio ippico tra la galleria di Marianopoli, ancora non ultimata, e la stazione omonima.

Con il completamento della galleria di Marianopoli, attualmente una delle più lunghe della Sicilia con i suoi 6482 metri, risultava possibile collegare su rotaia Palermo con Catania e, attraverso la linea ionica, con Messina.

La linea Palermo-Messina, via “Vallelunga”, rimase l’unico collegamento ferroviario diretto tra le due città fino alla conclusione dei lavori sulla linea tirrenica Cerda-Patti-Messina, datati 16 Giugno 1895.