Dzimis Madonā, kur bērnībā arī sācis futbolista gaitas pie trenera Broņislava Lipšāna, uz Rīgu pārcēlies 1972. gadā. Precējies, sieva Tatjana, meita Nadežda, dēls Sergejs. Absolvējis Rīgas Politehniskā institūta (RPI) Būvniecības fakultāti, Latvijas Valsts Fiziskās kultūras institūtu (LVFKI) un Maskavas Augstāko treneru skolu.

1975. gada beigās 20 gadu vecumā A. Starkovs debitēja padomju okupācijas laika galvenajā Latvijas Padomju Sociālistiskās Republikas (LPSR) meistarkomandā Rīgas “Daugava”, kas tobrīd vēl spēlēja Padomju Sociālistisko Republiku Savienības (PSRS) 2. līgā jeb pēc ranga trešajā padomju futbola līmenī. 1977. gadā A. Starkovs pārcēlās uz Maskavu, kur spēlēja PSRS kluba Maskavas “Dinamo” dublieru komandā, taču jau pēc gada viņš atgriezās Rīgā, kur drīz vien kļuva par “Daugavas” uzbrukuma līderi. 1981. gadā “Daugava” izcīnīja ceļazīmi uz PSRS futbola čempionāta 1. līgu, savukārt 1985. gadā “Daugava” ieguva pirmo vietu 1. līgā, taču papildu noteikumu dēļ tā neiekļuva PSRS futbola čempionāta Augstākajā līgā. “Daugavā” A. Starkovs spēlēja līdz pat 1989. gadam, ar 15 sezonās gūtajiem 189 vārtiem kļūstot par PSRS čempionātu visu laiku rezultatīvāko “Daugavas” spēlētāju.

Trenera karjeru A. Starkovs sāka vēl PSRS čempionāta pēdējā sezonā, 1991. gadā būdams Rīgas meistarkomandas “Pārdaugava” galvenā trenera Jāņa Skredeļa asistents. 1993. gadā A. Starkovs kļuva par 1992. gada Latvijas čempionvienības “Skonto” galveno treneri, izcīnīdams ar klubu 11 Latvijas čempionu titulus pēc kārtas (1992–2002). Tāpat šajā laikā “Skonto” sešas reizes izcīnīja Latvijas kausu (1992, 1995, 1997–1998, 2000–2001). No 1992. gada A. Starkovs divas sezonas bija pirmais jaunizveidotās Latvijas U-21 izlases galvenais treneris, bet 1995. gadā A. Starkovs darbu “Skonto” sāka apvienot ar Latvijas izlases galvenā trenera asistenta amatu, turpmākos sešus gadus palīdzēdams valstsvienības trenerim Jānim Gilim, gruzīnam Revazam Dzodzuašvili (რევაზ მიხეილის ძე ძოძუაშვილი) un anglim Gērijam Džonsonam (Gary Stephen Johnson).

05.2001. A. Starkovs tika iecelts par Latvijas futbola izlases galveno treneri. Ar valstsvienību A. Starkovs guva izcilus panākumus, palīdzēdams tai iekļūt 2004. gada Eiropas čempionāta  – tas ne tikai ir Latvijas futbola lielākais panākums, bet starptautiskās rezonanses ziņā ieņem īpašu vietu valsts sporta vēsturē. Lai kvalificētos Eiropas čempionāta finālturnīram 2004. gadā, Latvijas izlase pieveica tradicionāli spēcīgās Polijas, Ungārijas un Turcijas izlases, bet finālturnīrā nospēlēja neizšķirti ar titulēto pasaules futbola lielvalsti Vāciju.

2004. gada beigās A. Starkovs atvadījās no Latvijas izlases, lai ieņemtu galvenā trenera amatu pazīstamajā Krievijas klubā Maskavas Spartak, kur nostrādāja līdz 04.2006., 2005. gadā izcīnot Krievijas čempionāta sudraba medaļas. Maskavā A. Starkova vadībā spēlēja vairāki Eiropā labi pazīstami futbolisti, ieskaitot vēlāko titulētā Anglijas kluba Manchester United kapteini serbu Nemaņu Vidiču (Немања Видић). 06.2007. A. Starkovs veiksmīgi atgriezās Latvijas izlases galvenā trenera amatā – togad valstsvienība Starptautiskās Futbola federācijas (Fédération Internationale de Football Association, FIFA) pasaules izlašu rangā bija noslīdējusi uz 110. vietu, bet 11.2009. Latvijas izlase pacēlās uz savu visu laiku augstāko pozīciju FIFA rangā – 45. 2010. gada Pasaules kausa kvalifikācijas turnīrā Latvijas izlase līdz pat pēdējai spēlei cīnījās par ceļazīmi uz finālturnīru, bet izšķirošajā spēlē zaudēja Grieķijai (pirms tam Latvijas izlase uzvarēja Izraēlu un cīnījās neizšķirti ar Šveici). Kopā ar Latvijas izlasi A. Starkovs četras reizes izcīnīja Baltijas kausu futbolā (2001, 2003, 2008, 2012).

Valstsvienības vadīšanu A. Starkovs brīžiem apvienoja ar darbu klubos, 2010. gadā atgriezdamies “Skonto” galvenā trenera amatā un jau 12. reizi triumfējot Latvijas futbola virslīgā. 2011. gada sākumā A. Starkovs sāka trenēt Azerbaidžānas klubu FC Baku, kur gan nostrādāja tikai vienu gadu. 07.2013. A. Starkovs iesniedza atlūgumu no darba valstsvienībā, bet 02.2016. viņš atgriezās Latvijas izlasē kā galvenā trenera Mariana Pahara asistents. 04.2017. pēc M. Pahara atkāpšanās no amata A. Starkovs trešo reizi kļuva par Latvijas izlases galveno treneri, taču trešais piegājiens viņam vairs nebija veiksmīgs, un pieredzējušais treneris ar valstsvienību nostrādāja tikai gadu, līdz 04.2018. šķīrās no amata. Kopumā A. Starkova vadībā Latvijas futbola valstsvienība aizvadījusi 116 spēles (35 uzvaras, 23 neizšķirti, 58 zaudējumi).

2019. gadā A. Starkovs uz pusgadu kļuva par Latvijas futbola virslīgas kluba FK “Liepāja” galveno treneri, bet 2020. gadā sāka strādāt par Latvijas Futbola federācijas (LFF) izlašu direktoru, kura pienākumu lokā bija treneru darba analīze, rekomendāciju izstrāde spēlētāju attīstībai, pašmāju talantīgāko futbolistu identificēšana un viņu progresa sekmēšana.

A. Starkova vadītās komandas tradicionāli izcēlušās ar disciplinētu, taktiski gudru un pragmatisku spēles stilu, viņa vadībā futbola karjeru veiksmīgi izveidojuši un ārzemju klubos turpinājuši slavenākie Latvijas izlases meistari: Māris Verpakovskis, Marians Pahars, Vitālijs Astafjevs, Igors Stepanovs, Juris Laizāns, Andrejs Rubins, Imants Bleidelis, Andrejs Štolcers.

01.05.2010. A. Starkovam pasniegts Triju Zvaigžņu ordenis (IV šķira).

2004. gadā par godu Eiropas Futbola asociāciju savienības (Union of European Football Associations, UEFA) 50 gadu jubilejai veiktajā aptaujā LFF nosauca A. Starkovu par Latvijas 50 gadu (1954–2003) izcilāko futbolistu jeb “Zelta spēlētāju” (Golden Player). 2006. gadā LFF rīkotajā futbola speciālistu un žurnālistu aptaujā A. Starkovs tika iekļauts Latvijas futbola simtgades simboliskajā spēlētāju vienpadsmitniekā un arī tika atzīts par visu laiku labāko Latvijas futbola treneri. 2009. gadā A. Starkovs saņēma Latvijas Gada balvu sportā kā labākais treneris. LFF aptaujā A. Starkovs sešas reizes atzīts par Latvijas gada labāko futbola treneri (2000, 2002–2004, 2009–2010), turklāt šāda aptauja tiek rīkota tikai kopš 2000. gada.