Velleius Paterculus Valerius Maximushoz hasonlóan lojális az uralkodóházhoz és Tiberiushoz, s azt kifejezésre is juttatja történeti művében. Életéről csak azt tudjuk, amit két könyvből álló Historiae (Korunk története) című munkájában elárul önmagáról. Ahhoz a municipális nemesi réteghez tartozott, amely e korszakban fontos szerephez jutott. Anyai ágú ősei közt megemlíti Decius Magiust, aki a hannibali háborúk idején hű maradt Rómához, bár szülővárosa, Capua megadta magát Hannibalnak (2, 16, 2).
Atyai ágon nagyapja, C. Velleius a praefectus fabrum („főmérnök") tisztségét töltötte be Pompeius alatt, apja pedig praefectus equitum (a lovasság parancsnoka) volt Augustus idejében, és Tiberius Claudius Nerónak, Tiberius .császár apjának a pártfogását élvezte; ő maga pedig a lovasság parancsnoka Tiberius alatt. Ezen előzmények alapján érthető, hogy Velleius Paterculus Tiberius császár leghűségesebb emberei közé tartozott, s e korszak egyik legbefolyásosabb előkelőségének, M. Viniciusnak a baráti támogatását is remélhette.

A samniumi Aeclanumban született Kr. e. 20 körül. Tanulmányait feltehetően Rómában végezte, majd családjának tradícióit követve katonai pályára lépett. P. Silius és P. Vinicius — későbbi pártfogójának atyja — alatt katonai tribunusként szolgált Thraciában és Macedoniában (2, 101, 3). Gaius Caesar és Phraates parthus király találkozóján jelen volt (2, 101, 1-2), majd Tiberiust kísérte el praefectus equitumként Germaniába Kr. u. 4-ben. A quaesturát 6-ban nyerte el, azonban nem tölthette be, mert Tiberiushoz kellett mennie Pannoniába (2, 111, 3).

Alighogy visszatért Rómába, ismét vissza kellett utaznia legatus Augusti minőségben Tiberiushoz (2, 111, 4). 7 és 8 telét Sis-ciában tölti (2, 113, 3) és 9-ig Pannoniában marad (2, 114, 5-115, 1). 9 és 11 között Tiberius germaniai hadjáratában harcol, majd részt vesz Tiberius diadalmenetén 12-ben (2, 121, 3). 15-ben elnyerte a praeturát (2, 124, 4). Kr. u. 30-ban adta ki történeti művét. Ezen időpont után semmit sem tudunk róla. Lehet, hogy Seianus bukása őt is magával sodorta. Tény, hogy hosszasan magasztalja Seianust (2, 103, 4-5), s ebből lehetne arra következtetni, hogy Seianus családjával együtt bukott el, de ezt más adatokkal nem lehet megtámogatni.

Történeti művét M. Viniciusnak, egykori elöljárója fiának ajánlja, aki Tacitus szerint „Calesben született consuli apától és nagyapától, egyébként lovagi családból; szelíd természetű és ékesen szóló tehetség volt" (Annales 6, 15; fordította Borzsák I.). Tiberius őt választotta Germanicus lányának, Iuliának férjéül. Velleius ajándéknak szánta történeti művét pártfogójának abból az alkalomból, hogy az Kr. u. 30-ban elnyerte a consulságot.
Igen jó kapcsolatban állott patronusával, mert művében ismételten megszólítja (1, 13, 5; 2, 101, 3; 103, 1 stb.), sőt az időt olykor Vinicius consulságához viszonyítja (1, 8, 1 és 4; 2, 7, 5; 49, 1 stb.), ami azt jelenti, hogy művét legkésőbb 30 közepén befejezte, s amikor e részeket írta, már tudta, hogy Vinicius 30-ban consul lesz.
Ám az is lehetséges, hogy az anyaggyűjtést már korábban megkezdte - hiszen gyakran fontolgatta lelkében, hogy megírja Róma történetét (1, 16, 1) - s Vinicius consulsága szolgáltatott indokot arra, hogy tervezett művének egy rövidebb változatát elkészítse. Ezért hivatkozik többször arra, hogy sietnie kell munkájával (1, 16, 1; 2, 41, 1; 108, 2); e sietség miatt rövidnek kell lennie (2, 55, 1; 86, 1; 89, 1).

Az események bővebb tárgyalását egy igazi történeti alkotásnak tartja fenn (iusto servemus operi 99, 3), s a Varus-vereség tragédiáját igazi kötetekben igyekszik majd kifejteni (iustis voluminibus 119, 1). Ezt a többször beígért részletes történeti munkát Tiberius koráról azonban nem írta meg. Lehet, hogy a halál akadályozta meg ebben.