A mű eredeti címét nem ismerjük. Az editio princeps (1520) az első könyvnek a következő címet adja: Velleii Paterculi historiae Romanae ad M. Vinicium, a későbbi kiadások pedig a Velleii Paterculi historiarum ad M. Vinicium libri duo címet közlik, s ez utóbbi cím vált általánossá. Az editio princeps azon az egyetlen, ma már elveszett kódexen alapul, amelyet Beatus Rhena-nus Murbachban talált, a kolostor könyvtárában 1515-ben, igen rossz állapotban. A mű két könyvből áll.
Az 1. könyv csonkán maradt ránk: hiányzik a bevezetése, és a főszöveg egy része az elején, továbbá a 8. és 9. fejezet között is kiesett egy hosszabb rész. Az így fennmaradt 1. könyv 18 fejezetet foglal magában. Az első fejezet annak leírásával kezdődik, hogy a trójai háborúból visszatérő görög hősök milyen városokat alapítottak. Az első fennmaradt mondat azt mondja el, hogy Epeus alapította Metapontumot.
Valószínűnek tartható, hogy az 1. könyv a trójai háborúval kezdődött; Kr. e. 146-ig jutott el a történelmi események tárgyalásában. A 8. és 9. fejezet között kiesett rész Romulustól a pydnai csatáig tárgyalta az eseményeket, tehát hosszabb szöveg elveszésével számolhatunk. A 2. könyv jóval terjedelmesebb, s ez annak köszönhető, hogy szinte teljesen ránk maradt: 131 fejezetben 146-tól a szerző saját koráig tárgyalja az eseményeket oly módon, hogy az utolsó fejezetek Tiberiusnak és korának magasztalását tartalmazzák: a 14-től 30-ig eltelt 16 év eredményeit sorolják fel himnikus stílusban (126-131).

Velleius Paterculus Historiae ja több szempontból is figyelemre méltó. Róma történelmét a világtörténelembe ágyazva adja elő: a görög és a keleti városok kialakulása után jut el Karthágó (1, 6, 4), majd Róma alapításához (1, 8, 4). Karthágót szerinte 65 évvel Róma alapítása előtt a tyrusi Elissa hozta létre, akit egyesek Didóval azonosítanak. Rómát Romulus a hatodik olympias idején alapította a Palatium hegyen. A Város megszületésének évétől Vinicius consulságáig 781 év telt el. E számok is mutatják, hogy Velleius fontosnak tartja a kronológiát, s Róma eseményeit szívesen helyezi el világtörténelmi keretben.

Történeti művében nemcsak politikai történetet ad, hanem művelődés-, főleg irodalomtörténetet is. Minden nagyobb korszakban a politikai történet tárgyalása után kitér a szellemi élet ismertetésére. Például, miután leírta, hogy az ión telepesek, Ión vezetésével, elfoglalták Kis-Ázsia tengerpartját, és híres városokat alapítottak — Ephesost, Milétost, Kolophónt stb. —, rátér Homéros költői teljesítményének ismertetésére. Messze a legnagyobb költőnek tartja (Clarissimum deinde Homeri inluxit ingenium, sine exemplo maximum), mert nem volt előtte olyan költő, akit utánozhatott volna, sem utána olyan, aki őt tudta volna utánozni: neque ante ilium quem ipse imitaretur neque post ilium qui eum imitari posset inventus est (1, 5, 2). Erdekes, hogy Archilochost ugyanilyen nagy költőnek tartja a maga nemében. Homérost saját kora előtt 950 évre helyezi, Hésiodost pedig 120 évvel későbbre (1, 6, 7).
Athén virágkorának alkotóit is felsorolja, majd az újkomédia szerzőit (I, 16). Értékeli az első római alkotókat: Acciust a tragédia műfajában, Caeciliust, Terentiust és Afraniust a komédiában, Livius Andronicust, Catót, aki után űr tátong a római ékesszólásban — mondja —, amíg be nem robbant Cicero, „aki előtt csak kevés szónokban lelhetnéd gyönyörűségedet, csodálni pedig senkit sem csodálhatnál, csak azt, akit Cicero látott, vagy azt, aki Cicerót látta" (1, 17, 3-4).
A Gracchusok kora után is áttekintést ad az irodalomról. Különösen nagyra értékeli Afraniust, Pacuviust és Acciust, a szatíraíró Luciliust és e kor történetíróit: Sisennát, Coelius Antipatert, Claudius Quadrigariust és Valerius Antiast (2, 9, 1-6). Áttekintésének különössége, hogy nem említi Enniust és Plautust.

De nem érdektelen az sem, ahogyan az aranykor alkotóit értékeli, például a költők közül megemlíti Varrót, Lucretiust, és a náluk semmivel sem kisebb (neque ullo in suscepti operis sui genere minorem Catullum 2, 36, 2) Catullust. Nagyra értékeli tehát Catullust; annál feltűnőbb, hogy az augustusi kor költői között meg sem említi Horatiust, csak Vergiliust (princeps carminum), Tibullust és Ovidius Nasót, mert műfajukban a legtökéletesebbnek tartja őket: perfectissimi in forma operis sui (2, 36, 3). A történetírók közül mintha kiemelné Sallustiust azzal, hogy Thukydidés versenytársának mondj a (aemulumque Thucydidis Sallustium), bár Liviust is értékeli.

Velleius történeti munkája különös érdeklődésre tarthat számot a római provinciák kutatói között, mert mindkét könyvében található egy-egy kitérő. Az 1. könyvben a római coloniák történetét összegezi (1, 14-15), a 2.-ban pedig a provinciákét (2, 38-39). Az 1. könyvben azokat a coloniákat sorolja fel, amelyeket „a szenátus parancsára Rómának a gallok által történő elfoglalásától kezdve alapítottak" (1, 14, 1), mert szerinte ez tükrözi legjobban Róma katonai sikereit, illetve ez őrzi meg leginkább az alapítók hírnevét. Ismertetését az a tény teszi fontossá, hogy az egyes coloniák alapításával kapcsolatban mindig megemlíti, mikor történt és kinek a kezdeményezésére.
A 2. könyvben ugyanezt elvégzi a provinciákkal kapcsolatban, s eljárását azzal indokolja meg, hogy nem képtelenség (haud absurdum) azt, amit az egyes korok tárgyalásakor elszórtan megemlített, összegyűjteni és együtt tárgyalni, mert így világosabban kitűnik, milyen országot, ki és mikor szervezett át római provinciává, és ily módon a római birodalom fejlődését jobban át lehet tekinteni (2, 38, 1). Felsorolásából kitetszik, hogy a provinciaalapítás a dicsőség emlékműve is, például: „Syria és Pontus Cn. Pompeius erényének emlékműve" (2, 39, 1). De áttekintéséből az is egyértelmű, hogy a császári család tagjai: Iulius Caesar, Octavianus Augustus és Tiberius Caesar gyarapították a legnagyobb területekkel a birodalmat.

Abban viszont már a korábbi római történetírókat követi, hogy ahogyan közeledik saját korához, egyre részletesebben adja elő az eseményeket. Így tette ezt Cato az Originesben, de Livius is történeti művében, s ez természetes, hiszen ahogy haladt saját kora felé, egyre több forrás állt rendelkezésére, nem is szólva saját tapasztalatairól. Ez utóbbit Velleius Paterculusnál — ugyanúgy, mint Sallustius vagy a késő császárkorban Ammianus Marcellinus esetében — fontos tényezőnek kell tartanunk: aktív katonai parancsnok volt, követségek tagjaként sok olyan dologba volt betekintése, amely örökre zárva marad a szobatudós történetíró előtt.
E ténynek lehet betudni, hogy Marius tevékenységétől kezdve (2, 11) egyre részletesebb a beszámolója, s Augustus és Tiberius működésének sokkal nagyobb terjedelmet és figyelmet szentel, mint a korábbi államférfiaknak: a 2, 59-131. fejezetet. Továbbá azt, hogy az események ismertetésekor — mint láttuk — saját tetteire, szerepére és karrierjére is utal, mert szerinte ez is kora történetének része volt. Ugyanígy jár el később Ammianus Marcellinus is, aki katonaként szintén a történelmi események közvetlen alakítója és szemlélője volt.