Vaterpolo je počeo trenirati sa šest godina. Uspeo je da se, kroz vaterpolo izbori i sa problemima sa astmom, i postane jedan od najboljih vaterpolista sveta.[1]
Mladi Novljanin karijeru je započeo u Jadranu iz Herceg Novog. Nakon mlađih selekcija, sa 15 godina je zaigrao za prvi tim, a naredne tri godine je bio član najboljeg tima Jadrana. Bilo je to vreme u kojem je Jadran bio apsolutni šampion Srbije i Crne Gore. Tri puta za redom su bili pobednici Prvenstva i Kupa države.
Prelaskom u Partizan 2006. promenio se i šampion državnog Prvenstva i Kupa. Za pet godina u klubu sa Banjice, Prlainović je pet puta bio pobednik Prvenstva i Kupa Srbije. Pored toga, osvojio je dva puta Eurointer ligu, a u šampionskoj 2009/2010 Partizan i Prlainović bili su i šampioni Evrope nakon 35 godina.
Za odličnog Prlainovića zainteresovao se italijanski vaterpolo gigant Pro Reko i u leto 2011. srpski vaterpolista je uzeo kapicu kluba.[2] Uprkos titulama u Kupu i Prvenstvu Italije, pred početak Olimpijskih igara u Londonu 2012, italijanski klub je objavio da zbog problema sa finansijama mora da raskine ugovore sa strancima. Među njima našao se i Prlainović koji je nakon Igara pronašao novi klub.
Vratio se u Beograd, u Crvenu zvezdu sa ugovorom na godinu dana, uz mogućnost produženja.[3][4]Zvezda je te godine na čelu sa Dejanom Savićem sastavila tim od nekoliko reprezentativaca i mlađih igrača za velike uspehe. I još jednom je Andrija nastavio svoj šampionski pohod. Počeo ga je osvajanjem prvog Kupa Srbije za Zvezdu i to protiv Partizana u finalnom susretu. Usledila je i titula nakon 20 godina pauze, a naredne godine ponovili su isti uspeh. Na evropskoj sceni Zvezda je bila neprikosnovena. Kapiten Prlainović predvodio je tim do trofeja Liga šampiona.[5] i Superkupa Evrope Za svoje uspehe nagrađivan je od sportskog društva Crvene zvezde, ali uz sve napore, klub nije mogao da zadrži najboljeg prvotimca i najuspešnijeg kapitena - šest trofeja za dve sezone.
Naredna stanica za Prlainovića bila je Italija i povratak u Pro Reko.[6][7] Ovoga puta ugovor je potpisan na dve godine. Novih šest trofeja sa klubom iz Italije na svim takmičenjima. Za razliku od sezone 2011/2012, kada je osvajao Kup i Prvenstvo Italije, te Ligu šampiona, u sezoni 2014/2015 Prlainović je uz te, stigao i do novog trofeja i to u Superkupu Evrope. Nakon trijumfa sa Zvezdom, pehar i zlatnu medalju osvojio je i sa Pro Rekom.
Iz Italije Prlainović se preselio u Mađarsku i potpisao ugovor sa Solnokom. Nakon samo nekoliko utakmica, morao je na pauzu od tri nedelje zbog mononukleoze,[8], ali je to nadoknadio u narednim susretima. Stigli su do titule šampiona Evrope, a zatim i titule u Superkupu. Trijumfom u finalu Lige šampiona postao je jedini vaterpolista koji je sa četiri različita kluba četiri puta osvajao ovo takmičenje. Takođe, bio je najbolji pojedinac u finalnom susretu za titulu u Prvenstvu.[9] U sezoni 2017/2018 prvi put je ostao bez šampionske titule[10], a zbog povrede je propustio i završni turnir Lige šampiona.
Posle tri godine saradnje sa Solnokom, uz pad igre kluba Prlainović je odlučio da nastavi dalje.[11] Dogovorio je prelazak u Dinamo iz Moskve, ali su ti pregovori propali zbog smrti predsednika kluba. Ipak je ostao u Mađarskoj, ali je u Budimpešti zaigrao za OSC. U proleće 2020, u trenutku kada je vaterpolo sezona prekinuta zbog Korona virusa, klub iz Budimpešte je napustio glavni sponzor.[12] Niko od stranih igrača nije ostao u OSC.
Raspadom Srbije i Crne Gore 2006. godine odlučio se da igra za reprezentaciju Srbije čime počinje velika reprezentativna karijera igrača koji je zadužio kapicu sa brojem 11. Do sada je odigrao 321 utakmicu i postigao 519 golova.
Sa odličnim rezultatima u klubovima, 2008. debitovao je na Olimpijskim igrama u Pekingu i sa iskusnijim igračima stigao do bronzane medalje. Četiri godine kasnije, na letnjim olimpijskim igrama 2012. u Londonu on je bio jedan od onih iskusnijih. Na kraju turnira osvojio je ponovo bronzu, ali je sa 22 postignuta gola proglašen za najboljeg strelca turnira i uvršten u idealni tim. 2016. godine sa reprezentacijom Srbije osvojio je zlatnu medalju na Olimpijskim igrama u Riju.
Na Svetskom prvenstvu 2009. je debitovao kada su u pitanju ova takmičenja i odmah stigao do zlata. U Šangaju 2011. Srbija je u finalu poražena od Italije, ali je Prlainović uvršten u najbolji tim šampionata.[13]. Sedmi je bio 2013, dok je 2015. u Kazanju stigao dao zlata uz titulu najboljeg igrača prvenstva.
Novu bronzu osvojio je 2017. na šampionatu sveta u Budimpešti. Svetsko prvenstvo 2019. propustio je odlukom selektora da odmori igrače nakon ostvarene vize za Olimpijske igre u Tokiju.[14]
Andrija je nastupio na svih osam evropskih prvenstava koje je Srbija kao samostalna država odigrala. Debitovao je zlatom 2006. u Beogradu.I tad, ali i na svakom narednom davao je svoj maksimum. Usledilo je srebro u Malagi 2008, zatim bronza u Zagrebu uz odličan nastup Prlainovića. Od 2012. do 2018. osvojio je četiri zlatne medalje, uz to bio najbolji igrač šampionata u Beogradu 2016. U Budimpešti 2014. igrao je uz povredu ruke.
Sa juniorskom reprezentacijom Srbije i Crne Gore osvojio je Evropsko prvenstvo 2004. na Malti i 2006. u Oradeji.
Prvi gol na zvaničnoj utakmici bio mu je u finalu Svetske lige 2005. u pobedi protiv Mađarske. U takmičenju u kojem je postao rekorder.[15] Ima jednu bronzanu medalju osvojenu u Podgorici 2009. godine. Od 2005. do 2019. propustio je završnicu u Čeljabinsku 2013, kada je selektor odlučio da ga odmori od naporne sezone. Na završnom turniru Svetske lige 2019, u Beogradu stigao je do jubilarnog, 500. gola od kako je uzeo kapicu Srbije i to u utakmici protiv velikog sportskog rivala, reprezentacije Hrvatske.[16] Sa Mediteranskih igara ima jedno zlato (Peskara 2009) i jednu bronzu (Almerija 2005), a sa Svetskog kupa ima dva zlata, prvo iz Budimpešte 2006, a drugo iz Oradee 2010.
Andrija se 2014. oženio svojom dugogodišnjom devojkom Ivanom Čuljković[17] sa kojom ima dvoje dece. Andrija je sa dvojicom partnera 2015. krenuo u proizvodnju opreme za vodene sportove. Sponzorisali su klubove sa domaće scene, a postali su i zvanična oprema vaterpolo reprezentacije Srbije.[18]. Pored toga, sa sestrom vodi kafić u Beogradu. Poznat je kao neko ko uvek može da kaže svoje mišljenje i bori se za opstanak vaterpola u Srbiji. Učestvovao je u mnogim humanitarnim akcijama za pomoć deci, stanovništvu nakon poplava 2014. i mnogim drugim. Iz očiju saigrača, Prlainović je kompjuter u vodi i samo oni mogu da osete koliki je njegov doprinos u bazenu i reprezentaciji.
Šampion sa Partizanom
Šampion sa Jadranom
