Vitālijs piedzima un izauga Āgenskalnā, Rīgā. Sākotnēji futbolā trenējies Vitālija piecus gadus vecākais brālis Jevgēnijs, uz kura treniņu kādu dienu kopā ar vecākiem aizgājis arī tobrīd sešgadīgais Vitālijs. Salīdzinoši jaunā vecumā Vitālijs zaudēja abus vecākus, un tieši vecākais brālis deva lielu atbalstu viņa turpmākajā ceļā pretim futbola virsotnēm. Vitālijs mācījās Rīgas 61. vidusskolā Āgenskalnā, bet futbola treniņi bērnībā notika Mežaparkā. Vitālijs nereti intervijās atceras, ka tālo ceļu nereti mēroja pats, neizlaižot gandrīz nevienu treniņu.
Vitālijs Maksimenko jaunatnes karjeru pavadīja JFC Skonto sistēmā. Par pirmo profesionālo klubu kļuva Rīgas klubs FSK Daugava 90. Vitālija pirmais treneris līdz pat 18 gadu vecumam bija Vladimirs Beļajevs.
2009. gadā Vitālijs tika izīrēts Krievijas klubam Maskavas CSKA, kur spēlēja dublieru sastāvā. 2010. gada martā viņš pievienojās Skonto FC, kopā izcīnot Latvijas čempionu titulu, 2011. gadā — triumfējot Triobet Baltijas līgā, bet 2012. gadā – iegūstot Latvijas kausu. Rīgas komandas rindās viņš spēlēja arī UEFA Eiropas līgas kvalifikācijā.
2012. gadā Vitālijs tika atzīts par Skonto FC gada labāko spēlētāju un 2012. gada Virslīgas čempionāta labāko aizsargu.
2013. gada janvārī Vitālijs nokļuva Anglijas čempionāta klubā Brighton&Hove Albion, ar šo klubu noslēdzot līgumu uz diviem ar pusi gadiem. Tā paša gada martā klubs pieredzes iegūšanai nosūtīja Vitāliju uz līgu zemāk spēlējošo Yeovil Town komandu, ar kuru 2012./2013. gada sezonas izskaņā Wembley stadionā, Londonā, izdevās uzvarēt play off sacensībās un iegūt ceļazīmi uz Championship turnīru.
2014. gadā devās uz Skotijas čempionāta klubu Kilmarnock, bet nākamajā sezonā aizstāvēja Nīderlandes čempionāta kluba VVV-Venlo krāsas. 2015. gadā uz pavisam īsu brīdi - divas spēles Virslīgā - pievienojās SynotTip Virslīgas čempionāta klubam FK Liepāja, izceļoties arī ar skaitiem vārtiem, bet pēc tam parakstīja līgumu ar Austrijas augstākās līgas klubu SV Mattersburg.
Kopš 2017. gada visus Vitālijs vienu sezonu pārstāvēja Polijas Ekstraklasa klubu Bruk-Bet Termalica, kurā spēlēja vēl viens valstsvienības futbolists Vladislavs Gutkovskis. 2018. gada vasarā Vitālijs pievienojās Slovēnijas komandai Ļubļanas NK Olimpija. 2019. gada 30. maijā Vitālijs ar šo komandu triumfēja Slovēnijas kausa izcīņā, finālā ar 2:1 pārspējot 2018./2019. gada Slovēnijas čempioni Maribor, no kuras valsts čempionātā atpalika 9 punktus un ierindojās 2. vietā. 28 gadus vecais Maksimenko finālā aizvadīja visas 90 minūtes, bet sezonā kopumā piedalījās piecos kausa izcīņas mačos. 2018./2019. gada sezonā Slovēnijas čempionātā Vitālija kontā 29 spēles un divi vārti.
2020. gadu Vitālijs aizvadīja Japānas klubā "Omiya Ardija". Pandēmijas un ceļošanas ierobežojumu dēļ šī pārcelšanās uz Japānu negatīvi ietekmēja Maksimenko iespējas palīdzēt Latvijas izlasei, taču 2021. gadā viņš atgriezās Eiropā, atkal pārstāvot Slovēnijas "Olimpija" krāsas, un vēlreiz iekļāvās Latvijas izlases spēlētāju aptverē. 2021. gadā viņš ar "Olimpija" triumfēja Slovēnijas kausa izcīņā, finālmačā nospēlējot 89 minūtes.
Vitālijs Maksimenko regulāri spēlējis Latvijas jauniešu futbola izlases rindās. Kopā ar U-19 izlasi iekļuva un 2009. gadā spēlēja UEFA Eiropas U-19 čempionāta Elites raundā Francijā.
Iepriekš regulāri pieaicināts Latvijas nacionālās futbola izlases treniņiem, savu debijas spēli valstsvienības rindās kreisās malas aizsarga pozīcijā aizvadīja 2013. gada 6. februārī izbraukumā pret Japānu (0:3). Pirmos vārtus Latvijas izlasē Vitālijs guva pārbaudes spēlē 2015. gada martā Ļvivā pret Ukrainas izlasi, pēc stūra sitiena ar galvu panākot neizšķirtu (1:1).
Vitālijs ir trīskārtējs (2014., 2016., 2018.) Baltijas kausa ieguvējs Latvijas nacionālās izlases rindās.
Treneri Latvijā: V. Beļajevs, JFC Skonto/Daugava Riga (1996-2009), A. Starkovs, Skonto (2010-2011), M. Pahars, Skonto (2012), V. Dobrecovs, FK Liepāja (2015)