Paatero nousi kansanedustajaksi 1. helmikuuta 2006 varasijalta Sinikka Mönkäreen luovuttua kansanedustajan paikasta. Hänet valittiin kehitysministeriksiStubbin hallitukseen syyskuussa 2014.[2] Paatero nimitettiin Rinteen hallituksenkunta- ja omistajaohjausministeriksi 6. kesäkuuta 2019.[3][4] Hän ilmoitti pyytävänsä eroa ministerin tehtävistä 29. marraskuuta 2019. Pääministeri Antti Rinteen mukaan Paatero ei ollut noudattanut pääministerin Postin omistajaohjausta koskevia ohjeita.[5] Paateron kirjallisesti 2. joulukuuta jättämää eronpyyntöä valtioneuvoston jäsenyydestä ei käsitelty, koska Rinne jätti koko hallituksen eronpyynnön 3. joulukuuta 2019.[6]
Huolimatta aiemmasta eronpyynnöstään Paatero nimettiin kuntaministeriksi Rinteen hallitusta seuranneeseen Marinin hallitukseen.[7] SDP:n Tampereen puoluekokouksessa 2020 Paatero valittiin jatkamaan puoluevaltuuston puheenjohtajana vuodet 2020–2023. Puheenjohtajuudesta käytiin tiukka kamppailu Paateron ja turkulaisen Aki Lindénin välillä Paateron voittaessa äänin 252–237.[8]
Kansanedustajan toimen lisäksi Paatero on toiminut 2007–2016 urheilujärjestö TUL:n puheenjohtajana. Vuodesta 2000 alkaen hän on ollut kotikaupunkinsa Kotkan kaupunginvaltuutettuna.[9]
1 Maria Tolppanen erosi perussuomalaisista kesäkuussa 2016 ja liittyi sosialidemokraattiseen eduskuntaryhmään. 2 Nasima Razmyar siirtyi Helsingin apulaispormestariksi kesäkuussa 2017, ja hänen tilalleen eduskuntaan nousi Pilvi Torsti.
3 Susanna Huovinen siirtyi Keski-Suomen ensi- ja turvakodin toiminnanjohtajaksi kesäkuussa 2018, ja hänen tilalleen eduskuntaan nousi Riitta Mäkinen.