Empresa creada en 1877 bajo los auspicios de empresarios malagueños ligados a la pionera industrialización andaluza con la construcción del ferrocarril de Córdoba a Málaga. Rápidamente fue ampliando su red por casi toda Andalucía. Así se incorporarían las líneas de Sevilla-Jerez-Cádiz, Utrera-Morón-Osuna, Osuna-La Roda, Jerez-Sanlúcar-Bonanza, Marchena-Écija, Campillos-Granada y Córdoba-Belmez. A finales del siglo XIX se le incorporan las líneas de Puente Genil-Córdoba y Écija-Córdoba, además de la de Alicante-Murcia, única que explotó fuera del territorio andaluz.

En 1913 adquiere la línea de Bobadilla-Algeciras y en 1916 toma en arriendo las líneas de la Compañía de los Ferrocarriles del Sur de España, que definitivamente adquiere en 1929.

Los graves problemas financieros llevaron a la incautación de Andaluces por parte del Estado en 1936, quien la entrega a la Compañía Nacional de los Ferrocarriles del Oeste, creándose la Compañía Nacional de los Ferrocarriles del Oeste y Red de Andaluces, que conservaron siempre una explotación separada hasta su incorporación a Renfe en 1941.