He went to Mauretania with the rank of praetor in AD 42 to suppress a revolt and soon earned promotion to legatus legionis. He was the first Roman to cross the Atlas Mountains. In 59 he received command of the army in Roman Britain and became Governor General of the territories there.
Paullinus acted vigorously in suppressing revolt, especially in Wales, but he was campaigning against the druids of Mona when Boudicca razed Camulodunum (circa 60) and he had to race southwards. He could not reach Verulamium or Londinium, and both settlements suffered heavy damage. Paullinus advanced down Watling Street to choose a battlefield to his advantage. The two armies met at an unknown location, believed to lie in the Midlands near Manduessedum near the modern day town of Atherstone in Warwickshire. The discipline of the 14th legion sufficed to rout the numerically superior Britons. According to Tacitus 20,000 Roman troops faced around 100,000 Britons. The army of Boudicca advanced straight at the waiting Romans, but when the forces met the superior weapons and discipline of the legionaries forced them back. Tacitus states that the Britons' own baggage train then prevented their flight, and defeat turned into slaughter. Possibly 80,000 Britons died, while Roman casualties remained under 1,000. (The British casualties included women and children, for families accompanied the combatants.)
The emperor Nero recalled Paullinus from Britain in 62, soon after his victory.
Paullinus became a consul ordinarius in 66. Following the death of Servius Sulpicius Galba in January 69, Paullinus agreed to lead the forces of Marcus Salvius Otho against the supporters of Aulus Vitellius, and won a victory near Cremona against Aulus Caecina Alienus. But Otho suffered a decisive defeat at Bedriacum. Despite fighting on the losing side, Paullinus received a pardon in 69. His eventual fate remains unknown.