Paterculus belonged to a distinguished Campanian family, and entered the army at an early age. He served as military tribune in Thrace, Macedonia, Greece and the East, and in AD 2 was present at the interview on the Euphrates between Gaius Caesar, grandson of Emperor Augustus, and the Parthian king Phraataces. Afterwards, as praefect of cavalry and legatus, he served for eight years (from AD 4) in Germany and Pannonia under Tiberius. For his services he was rewarded with the quaestorship in AD 8, and, together with his brother, with the praetorship in AD 15. He was still alive in AD 30, for his history contains many references to the consulship of M. Vinicius in that year. It has been conjectured that he was put to death in AD 31 as a friend of Sejanus, whom he praises.
His Compendium of Roman History consists of two books dedicated to M. Vinicius, and covers the period from the dispersion of the Greeks after the siege of Troy down to the death of Livia (AD 29). The first book brings the history down to the destruction of Carthage, 146 BC; portions of it are missing, including the beginning. The later history, especially the period from the death of Julius Caesar, 44 BC, to the death of Augustus, AD 14, is treated in much greater detail. Brief notices are given of Greek and Roman literature, but no mention is made of Plautus, Horace or Propertius. The author does not display real historical insight, although generally trustworthy in his statements of individual facts. He may be regarded as a courtly annalist rather than an historian. His chronology is inconsistent. On Caesar, Augustus and above all on his patron Tiberius, he lavishes praise or flattery. The repetitions, redundancies, and slovenliness of expression may be partly due to the haste with which (as the author frequently states) it was written. The inflated rhetoric, the straining after effect by means of hyperbole, antithesis and epigram, belong firmly to the Silver Age, of which Paterculus is the earliest example. He purposed to write a fuller history of the later period, including the civil war between Caesar and Pompey and the wars of Tiberius; but there is no evidence that he did so. His chief authorities were Cato's Origines, the Annales of Q Hortensius, Pompeius Trogus, Cornelius Nepos and Livy.
In Harry Turtledove's "Historical Note" at the end of his Give Me Back My Legions! he refers to Velleius Paterculus' history as one of the sources for his novel. Turtledove indicates modern historians do not hold this work in high regard but he had served in Germany and was a contemporary and colleague of some of those involved in the campaign. Also, he is the sole source of information about some of these individuals. Turtledove appears to have used this history as background information for Lucius Eggius, Vala Numonius, and Caldus Caelius much the way he used the historical records of the 47th North Carolina for characters in The Guns of the South.