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 Rhenanus 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).