El primer edificio de viajeros con el que contó la ciudad de Cádiz fue una construcción provisional cuya existencia se iba a prolongar en el tiempo debido a los problemas surgidos con su emplazamiento definitivo. Este primer edificio era de una sola planta y  fue construido en madera, a modo de un barracón, como había sido habitual en otras muchas estaciones de la época. Tenía una longitud aproximada de 139,50 metros y una anchura de 13,50 metros. Estaba dividido en tres tramos y se completaba con sus correspondientes marquesinas.

La concesión de la línea se realizó en el año 1856, y con ella se construyó la primera estación en las inmediaciones de las murallas de la ciudad, zona que pertenecía al Ministerio de la Guerra. Se entabla así un conflicto de intereses que debían resolver, por un lado, la compañía ferroviaria que argumentaba un mejor servicio al público, y por otro lado, el Ministerio de la Guerra que hacía lo propio en cuanto a la situación de sus instalaciones. El conflicto se resuelve a través de una comisión que propone una serie de requisitos para la aprobación de la nueva estación de ferrocarril.

Los primeros proyectos se realizaron hacia 1890, y sobre éstos se realizarían otros posteriores que fueron introduciendo algunas modificaciones hasta que se termina aprobando por Real Orden de 4 de enero de 1902. El edificio que adopta la tipología de estación término, fue realizado por el ingeniero Agustín S. de Jubera, aunque como ya se ha dicho, sobre la base de otros proyectos anteriores.

Su composición se estructura a través de dos pabellones paralelos de 104 metros de longitud, uno a cada lado de las vías, en correspondencia con su tipología. Uno de los lados se destinaba al servicio de llegadas, y el otro al servicio de salidas. La fachada principal se disponía de forma simétrica, a partir de sus dos pabellones laterales de dos plantas unidos por el testero de la cubierta, que consistía en una estructura metálica con forma triangular cerrada en su frontal mediante acristalamiento. El espacio central que ocupaba este frontón triangular quedaba cerrado en su parte inferior por una verja. La estructura metálica que cubre el espacio central de los andenes y vías tenía 31 metros de luz, y para su construcción se emplearon cerchas de tipo inglés. La cubierta se sustentaba sobre apoyos también metálicos que dan al exterior en sus muros, conformando grandes arcos rebajados que a su vez alojaban otros de medio punto.

El edificio emplea el lenguaje ecléctico, con elementos clasicistas que realzan sus formas a través de una ornamentación contenida, sobria y elegante, que combina perfectamente con las formas innovadoras que ofrecen la presencia del hierro y el vidrio.

Las obras de cimentación del edificio de viajeros comenzaron en el año 1894, pero por motivos administrativos en el proceso de aprobación del proyecto sufrieron retrasos importantes, hasta el punto de que las obras no se concluyeron hasta el año 1906.

Actualmente se están llevando a cabo las obras de rehabilitación del edifico para adaptarlo en un complejo gastronómico y de ocio que, presumiblemente abrirá a finales del año 2018.