Marko on sündinud 30. novembril 1969 Valgas, kus ta 1988. aastal lõpetas keskkooli. Sama aasta suvel oli Marko Valga Muinsuskaitse Seltsi asutajate seas ning oli üks nendest, kes heiskas 24. veebruaril 1989 Valgas sini-must-valge lipu. Samal päeval luges ta Valga rahvale kultuurimajas ette Eesti iseseisvusdeklaratsiooni.
Ajalooõpingud Tartu ülikoolis lõpetas Marko cum laude 1993. aastal, kui ta oli juba tööle asunud ajalehe Postimees välisuudiste toimetuses. Ajaloostuudiumi käigus keskendus Marko Venemaa ajaloole ning tema asjatundlikud kirjutised Postimehes pälvisid kiirelt lugejate huvi.
1994. aasta augustis saatis Postimehe toimetus Marko korrespondendiks Venemaale Moskvasse. Keerukad aastad Venemaa ajaloos pakkusid ajakirjanikutööks piiramatul hulgal teemasid. Marko kirjutas kolme ja poole aastaga enam kui tuhat lugu, mille hulgas olid sõjakajastused Tšetšeenias ning intervjuud Venemaa tipp-poliitikutega. Kõik see andis hindamatu kogemuse Venemaa paremaks mõistmiseks.
Tšetšeenia komandeeringute käigus tuli Markol 1996. aasta märtsis üle elada ka lühiajaline vangistus koos fotograaf Tõnu Nooritsaga, kui parasjagu koguti materjale ajakirja Luup kaanelooks. Õnnelik juhus päästis mehed halvimast.
1997. aasta lõpus sai Markost ajalehe Postimees peatoimetaja. Tema juhtimisel viidi ellu toimetuse üleviimine Tartust Tallinna, mis tagas ajalehele jätkuva juhtpositsiooni Eesti leheturul.
2000. aastal lahkus Marko Postimehest ning asus tööle aasta varem loodud Balti Venemaa Uurimise Keskuse juhina. 1999. aastal kaitses Marko Tartu Ülikoolis ajaloomagistri kraadi Venemaa poliitilistest arengutest Nõukogude Liidu lagunemise eel ja järel. 2010. aastal avaldas ta kirjastuses Varrak oma esimese raamatu “Venemaa: valguses ja varjus”, milles ta sulandas akadeemilise, ajakirjaniku ja poliitiku vaatenurga Venemaa arengutele alates 1970. aastate lõpust tänapäevani. 2019. aasta algul ilmus Markolt teine raamat nimega “Murdeajastu”. Raamatus avab talaiale lugejaskonnale huvipakkuvalt oma nägemuse sellest, kuidas maailm on meie ümber läbi tegemas ajaloo suurimat murdehetke. Käsitlemist leiavad teemad Venemaast Hiinani ja kliimamuutustest sõltumatute inimesteni. Marko on samuti kahe õpiku kaasautor ning koos Mart Laariga on ta avaldanud raamatu Ida- ja Kesk-Euroopa reformikogemusest.
2001. aastal liitus Marko paremtsentristlikku maailmavaadet esindava erakonnaga Res Publica ja 2003. aastal valiti ta X Riigikogu liikmeks. Markost sai väliskomisjoni esimees, kusjuures komisjoni liikmeteks selle algusaegadel olid ka hilisem president Toomas Hendrik Ilves ja eurovolinik Siim Kallas.
XI Riigikogu koosseisus oli Marko Euroopa Liidu asjade komisjoni esimees, olles samas ka väliskomisjoni liige. 2011. aastal valiti Marko kolmandat korda Riigikokku ning temast sai taas väliskomisjoni esimees. 2015. aastal valiti Marko neljandat korda parlamenti. Esmalt oli ta riigikaitsekomisjoni esimees ja alates 2016. aasta novembrist taas väliskomisjoni esimees. Marko on Riigikogu liikmena 16 aasta jooksul mõjutanud oluliselt Eesti välis- ja julgeolekupoliitikat, pidades alati oluliseks Eesti välisteenistuse ja välismajandusvõimekuse tugevdamiset. Sama jätkab ta ka Riigikogu XIV koosseisus, kuhu ta valiti 2019. aasta märtsis. Praegu on Marko väliskomisjoni aseesimees.
2017. aastal tegi Marko enda jaoks raske otsuse ning lahkus IRLi ridadest. Peamiseks põhjuseks sai erakonna taandumine sügavasse konservatismi, mis ei ühtinud enam Marko liberaalsemate vaadetega. 2018. aasta septembris otsustas Marko liituda Reformierakonnaga.
Parlamendipoliitikuna on Marko juhtinud Eesti delegatsiooni nii Euroopa Nõukogu Parlamentaarses Assamblees (2003-2007) kui ka NATO Parlamentaarses Assamblees (2011-2019). Seejuures õnnestus paljuski tänu Marko aktiivsele rollile võtta 2006. aastal esimest korda rahvusvahelisel parlamentaarsel foorumil vastu kommunismi kuritegusid hukkamõistev resolutsioon. Marko on põhjalikult tegelenud ka energiajulgeoleku teemadega, kusjuures 2006. aastal esitas ta Strasbourgis raporti energiatarnete kasutamisest Venemaa poolt välispoliitiliste eesmärkide saavutamisel.
Ühiskondlikus tegevuses on Marko Eesti NATO Ühingu nõukogu esimees ja Rahvusvaheliste Kaitseuuringute Keskuse nõukogu liige. Samuti kuulub ta Kaitseliidu Harju malevasse ja reservohvitserina (nooremleitnant) Eesti Reservohvitseride Kogusse.
Marko on avaldanud artikleid nii Eesti kui rahvusvahelises meedias, sealhulgas sellistes väljaannetes nagu Le Monde, International Herald Tribune, The Washington Times, The Moscow Times, EUobserver, Europe’s World. Intervjuusid on ta andnud Financial Timesile, The Economistile, mitmetele rahvusvahelistele tele- ja raadiokanalitele, sealhulgas näiteks otse-eetris Al Jazeerale.
Eraelus on Marko kõrval kaunis Tuuli Semevsky, kes on tõlkebüroo omanik ja hinnatud keelekoolitaja. Varasemast kooselust on Markol 15-aastane tütar Rosemary, kes õpib praegu Inglismaal.
Marko peab oluliseks aktiivset ja tervislikku eluviisi. Kui kooliajal oli lemmikuks spordialaks korvpall, siis hiljem on ta harrastanud jalgpalli, ratsutamist, tennist ja golfi. Ratsutamises õnnestus Markol 2001. aastal tulla koguni Eesti amatööride meistriks takistussõidus.