Spēlējis dažāda vecuma Latvijas jauniešu izlasēs, 09.06.1999. M. Verpakovskis 19 gadu vecumā debitēja Latvijas valstsvienības sastāvā Eiropas čempionāta kvalifikācijas spēlē Atēnās, ar gūtajiem vārtiem palīdzot izcīnīt uzvaru 2:1 pār Grieķiju. M. Verpakovska zvaigžņu brīdis pienāca 2003. gada rudenī, kad lielā mērā tieši liepājnieka rezultatīvā spēle ļāva Latvijas izlasei sensacionāli izcīnīt ceļazīmi uz 2004. gada Eiropas čempionāta finālturnīru. “Euro 2004” atlases turnīrā M. Verpakovskis piedalījās visās desmit spēlēs un guva sešus vārtus, izceļoties ar pieciem rezultatīviem sitieniem pēdējos četros izšķirošajos mačos. Vispirms 2003. gada septembrī M. Verpakovskis ar diviem vārtu guvumiem nodrošināja uzvaru 3:1 Rīgā pār Ungāriju, bet pēc mēneša viņš guva vienīgos vārtus viesu mačā ar Zviedriju (1:0), ļaujot izcīnīt otro vietu kvalifikācijas grupā un tiesības aizvadīt pārspēles par vietu finālturnīrā pret Pasaules kausa bronzas medaļu ieguvējiem Turciju. Pirmajā mačā Rīgā 15.11.2003. M. Verpakovskis guva vienīgos vārtus (1:0), bet atbildes mačā Stambulā 20.11.2003. viņš panāca neizšķirtu 2:2, Latvijas izlasei izcīnot uzvaru divu spēļu summā. Nākamajā vasarā “Euro 2004” finālturnīrā 15.06.2004. M. Verpakovskis guva vēsturiskus vārtus, izvirzot komandu vadībā pirmajā mačā pret Čehiju (1:2). Latviešu uzbrucējs spilgti aizvadīja arī otro čempionāta spēli pret Vāciju, lai gan šoreiz neguva vārtus, bet Latvijas komanda izcīnīja sensacionālu neizšķirtu 0:0 pret Eiropas titulētāko futbola izlasi.
M. Verpakovskis turpināja spēlēt Latvijas izlasē līdz pat 2014. gadam, pēdējo reizi valstsvienības rindās izejot laukumā dzimtajā Liepājā 29.05.2014. Baltijas kausa mačā pret Igauniju (0:0). Ar 29 gūtajiem vārtiem M. Verpakovskis kļuva par valstsvienības visu laiku rezultatīvāko spēlētāju. Šo rekordu viņš sasniedza 13.10.2007., gūstot divus vārtus Eiropas čempionāta kvalifikācijas mačā Reikjavīkā pret Islandes izlasi (4:2) un apsteidzot Ēriku Pētersonu, kurš pirms Otrā pasaules kara valstsacīkstēs guva 21 vārtus. Aizvadījis 104 valstsacīkstes, M. Verpakovskis ir sestais spēlēm bagātākais Latvijas izlases spēlētājs vēsturē.