Rzeszów WschódRzeszów Wschód – Jarosław ZachódJarosław Zachód – KorczowaKorczowa – granica państwa
thumb|Konkurujące drogi dla odcinka pod zarządem Stalexport Autostrada Małopolska
W 1995 r. Agencja Budowy i Eksploatacji Autostrad ogłosiła przetarg na przystosowanie do odpłatności i eksploatację autostrady A4 na odcinku Katowice – Kraków. Złożono trzy oferty z których tylko jedna, złożona przez Stalexport SA, przeszła do drugiego etapu. 19 września 1997 Minister Transportu i Gospodarki Morskiej udzielił Stalexport SA koncesji na eksploatację oraz przystosowanie odcinka Katowice – Kraków do wymogów płatnej autostrady, za koncesję firma zapłaciła skarbowi państwa 3 mln dolarów. .
Umowa koncesyjna zawarta pomiędzy skarbem państwa i Stalexport Autostrada Małopolska była źródłem licznych kontrowersji. Jeden z jej zapisów ogranicza możliwości rozbudowy dróg alternatywnych w stosunku do odcinka Katowice Murckowska – Brzęczkowice. Każde podniesienie jakości lub przepustowości dróg równoległych do tego odcinka może być traktowane jako droga konkurencyjna i skutkować odszkodowaniami dla operatora autostrady.