Budowa autostrady rozpoczęła się w 1992 roku, kiedy odcinek między Antequera a Malagą został zbudowany jako modernizacja N-331. W 2003 roku zmieniono numerację na A-45 w ramach ogólnej zmiany numeracji hiszpańskich autovías . Odcinek między Córdoba i Benamejí został zbudowany w połowie 2000 roku, biegnąc równolegle do N-331, a odcinek między Benamejí i Antequera został zbudowany w 2009 roku.
Odcinek między Puerto de Las Pedrizas, kilka kilometrów na południe od Antequera, a Malagą jest często używany przez kierowców podróżujących do i z Kordoby, Sewilli (przez Autovía A-92 ) i Granady (przez Autovía A-92M i A-92) . Pod koniec 2000 i na początku 2010 roku Autopista AP-46 została zbudowana w celu odciążenia ruchu na tym odcinku.
