Hänen pääteoksestaan Roman historia (vuodelta 78 vuoteen 67) on meidän aikoihin säilynyt ainoastaan katkelmia. Sitä vastoin ovat aivan täydellisinä meillä tallella kuvaus Katilinan kapinaliitosta ja sota Jugurthaa vastaan.
Kuvauksensa Sota Jugurthaa vastaan aloittaa hän vertaamalla persoonallisten etevyyksien ja rikkauksien katoovaisuutta henkisellä alalla tehtyjen urotöiden pysyväisyyteen; kunnianhimoa, joka oli kiihoittanut muinaisuuden mainioita miehiä seuraamaan esi-isiään mainetta ja kunniaa saavuttakseen, aikansa tapain turmelukseen, kun ihmiset kilvan koettivat kunnostaa itseään ylellisyydellä ja laiskuudella enemmän kuin hyveellä ja työllä. Hän johtaa sitte lukijansa muistamaan, miten Hannibal toisessa Punilaisessa sodassa enemmän kuin mikään muu vihollinen oli heikontanut Roman voimaa, ja että oli tehty liitto Numidialaisten kanssa, joiden kuningas Micipsa oli kasvattanut veljenpoikansa, nimeltä Jugurtha, yhtä huolellisesti kuin omatkin poikansa. Kun Jugurtha oli kasvanut mieheksi, saavutti hän rohkeudellaan ja viisaudellaan sekä omien maanmiestensä että Romalaisten kenraalien suosion, ja hänen setänsä oli kuollessaan palkaksi urhoudesta, jota Jugurtha oli osoittanut Numantian piirityksessä, perinnöksi määrännyt hänelle toisen puolen valtakuntaansa.
Jaettuaan aarteet ja maat serkkujensa kanssa murhautti Jugurtha nuoremman heistä, Hiempsalin, ja pakoitti vallanhimoisilla pyyteillään vanhemman, Adherbalin, pakenemaan Romaan valittamaan senaatille. Peläten rangaistusta, laitti Jugurtha lähettiläitä Romaan, jotka runsailla lahjomisilla saivat aikaan, että senaatti, tekemättä mitään Hiempsalin murhan kostamiseksi, päätti jakaa Numidian molempien valtaan pyrkijöiden välillä; ja Jugurtha toimitti niin, että hedelmällisimmät ja väkirikkaimmat maat tulivat hänen osalleen.
Sallustius kertoo nyt Afrikan asemasta ja sen asukkaista, mainiten useimpien kirjailijoiden pitävän sitä kolmantena maanosana. Pohjoisrannikolla asui alkuaan ainoastaan Getuleja ja Libyalaisia, ja myöhemmin Medialaisia ja Persialaisia, jotka olivat sotilaina palvelleet Herkulesta Hispaniassa. Nimen Medialaiset olivat Libyalaiset vähitellen vääntäneet nimeksi Maurilaiset; ja Getulien sekä Persialaisten jälkeläiset olivat perustaneet Numidian valtakunnan. Sitä myöhempänä aikakautena perustivat Foinikialaiset ja muut siirtolaiset useita kaupunkeja, ja Kyrenen asukkaista kasvoi mahtava kansa. Toisella puolen heitä asuivat Etiopialaiset, ja kauempana etelässä päin alkoi pitkä jono auringon paahtamia maita. Siihen aikaan, jolloin sota Jugurthaa vastaan alkoi, hallitsivat useampia punilaisia kaupunkeja Romalaiset preetorit; Maurilaisten hallitsijana oli kuningas Bocchus.
Vakuutettuna siitä että Romassa kaikkea saattoi ostaa rahoilla teki Jugurtha uudelleen hyökkäyksen Adherbalin alueelle ja piiritti Cirta-kaupunkia, nykyistä Konstantinea Algierissa. Roman senaatti lähetti ruhtinaille käskyn, että heidän pitäisi lykätä riitansa erityisen tuomiokunnan ratkaistavaksi, mutta Jugurtha vakuutti ainoastaan ryhtyneensä varokeinoihin estääkseen Adherbalin vehkeitä, ja sillä vastauksella läksi lähettiläs kotiin. Adherbal lähetti nyt vuorostaan valituskirjeen senaatille, jonka jälkeen laitettiin uusi lähetyskunta varoittamaan Jugurthaa. Mutta siitä ei lähtenyt mitään hyötyä, ja kun Cirta oli pakoitettu heittäytymään viholliselle, surmattiin Adherbal ja hänen kanssaan kaikki kaupungin asukkaat. Nyt lähetettiin sotajoukko konsuli Kalpurnion johdolla Numidiaan. Jugurtha kuitenkin lahjoi päällikön, ja vale-antautumisen jälkeen, joka maksoi Jugurthalle muutamia norsuja ja nautaeläimiä, mitkä hän sittemmin sai takaisin, palasi konsuli Romaan. Mutta kansantribuni Memmius, joka vihasi ylimyksiä, yllytti kansaa vaatimaan että Jugurtha noudatettaisiin Romaan ja pantaisiin kanteesen. Se tapahtuikin, ja Jugurthaa käskettiin ilmaisemaan rikoskumppaninsa, uhalla että muuten surmattaisiin. Mutta toisen tribunin, Boebion, avulla, jonka Jugurtha oli lahjonut, teki hän tyhjäksi kansankokouksen päätöksen. Jugurtha, joka sitä paitsi runsaalla lahjomisella oli saanut erään uuden kilpailijansa salaa surmatuksi, sai nyt käskyn heti lähteä Romasta, ja hän tekikin sen sanoen: "Kurja kaupunki, sinut saisi kokonaan ostaa ja hävittää, jos vain löytyisi ostaja!" Kun sotaa häntä vastaan nyt jatkoi konsuli Albinus, saarsi hän öiseen aikaan romalaisten leiriin ja pani vastustajansa niin ahtaalle, että tämän täytyi myöntyä mitä häpeällisimpiin rauhan ehtoihin. Mutta senaatti julisti, ettei mitään rauhaa voitaisi tehdä ilman sen ja kansan suostumusta, ja tutkijakunta asetettiin vetämään kanteen alaisiksi ja rankaisemaan niitä, jotka olivat ottaneet lahjoja viholliselta.
Sallustius huomauttaa tässä ohimennen Punilaisten sotien loputtua syntyneen mahtavia puolueita sekä kansassa että senaatissa; patriciot — ylimykset — olivat kohottaneet valtavaatimuksensa, ja plebejit — alhainen kansa — vapausvaatimuksensa niin korkealle, että ne uhkasivat valtiolle perikatoa.
Metellus, toinen uusista konsuleista, voimakas ja rehellinen mies, tuli nyt Numidiassa Roman sotajoukon päälliköksi ja sai Jugurthasta ja tämän kenraalista Bomilkarista tärkeän voiton, joka herätti suurta riemua ja tyytyväisyyttä Romassa; mutta vihollisuuksia jatkettiin kuitenkin vaihtelevalla onnella. Kertomuksen päähenkilöksi tulee nyt Marius, Metellon alipäällikkö, jonka onnistui itselleen saada lupa palata Romaan, jossa hän valittiin konsuliksi. Sillä aikaa lisäsi Jugurtha sotavoimaansa pestaamalla Getuleja ja yllytti Mauretanian kuningasta Bocchoa julistamaan Romalaisille sotaa. Sallustius kertoo nyt muutamia hauskoja tapauksia, ja hänen kuvauksensa taisteluista, maan luonnosta, kansan tavoista ja sotajuonista, joita taistelijat käyttivät voittaakseen toisensa, ovat hyvin hauskoja. Metellus nolostui niin vastarinnasta, jota hänelle tehtiin, että hän, siihen sijaan kuin hänen olisi pitänyt voimakkaasti jatkaa sotaa, koetti välttää yhteeniskemistä. Sillä välin oli Marius osannut saattaa Metellon epäluulon alaiseksi ja samalla herättänyt kansassa suuria toiveita itsestään, jos pääsisi ylipäälliköksi. Se onnistuikin; Metellus kutsuttiin pois ja Marius valittiin hänen seuraajakseen.
Kun Marius oli saapunut Afrikaan ja niin vähitellen totuttanut mukanaan tuodut apujoukot pelotta kohtaamaan vihollista, valloitti ja poltti hän monta tärkeätä kaupunkia ilman mainittavaa mieshukkaa Romalaisten puolelta, josta oli seurauksena, että Numidialaiset alkoivat pelätä häntä ylenluonnollisena olentona. Keskellä näitä voittoja tuli Marion sotajoukkoon lisäksi suuri ratsujoukko; sen oli Romassa koonnut Marion kvestori Sulla; häntä Sallustius esittää jalosukuiseksi mieheksi, joka suosi kirjallisuutta ja nautintoa, mutta rakasti vielä enemmän kunniaa ja oli varustettu ominaisuuksilla, mitkä pian tekivät hänet sekä Marion että halvimpien sotamiestenkin suosikiksi. Bocchus oli nyt liittynyt Jugurthaan, ja yhdistynein voimin viskautuivat he niin tulisesti Romalaisten päälle, että näiden mieshukka oli suurempi kuin kaikissa edellisissä taisteluissa yhteensä. Uudessa tappelussa paria päivää myöhemmin lyötiin barbarit uudelleen, ja Bocchus, jonka Marion luo lähetyt lähettiläät joutuivat rosvojen kynsiin ja Sullan ruokittaviksi, saatiin laittamaan lähettiläitä Romaan rauhaa rukoilemaan. Senaatin luvattua hänelle ystävyyttä ja liittoa, jos hän sitä ansaitsisi, pyysi hän päästä keskustelemaan Sullan kanssa. Se hänelle myönnettiinkin, mutta Sulla tuli paikalle vahvan vartiojoukon turvissa, jossa oli myös muutamia Balearialaisia linkojia, ja kuninkaan poika Volux tuli hänelle vastaan. Sulla, jota oli kehoitettu olemaan varuillaan, koska Jugurthan luultiin olevan lähiseuduilla, aavisti petosta, mutta kehoitti sotamiehiään pysymään rohkealla mielellä. Ei koskaan aseellisen miehen, sanoi hän, tarvitse kääntää selkäänsä viholliselleen. Ja niin saapuivat he vahingoittumattomina Maurilaisten leiriin. Yksityisessä neuvottelussa sitoutui Bocchus hiukan epäröittyään pettämään Jugurthaa. Tämä houkuteltiin useimpine seuralaisineen aseitta tulemaan muka rauhanpäätöksestä keskustelemaan. Väijyksistä hyökättiin heidän päälleen, ja Jugurtha jätettiin sidottuna Sullalle, joka vei hänet Mariolle. Itse ei Sallustius enempää kerro Jugurthasta, mutta muilta saamme me tietää, että hän ja kaksi hänen poikaansa kuletettiin vankeina triumfiretkessä Romassa. Kansan pilkkaamana ja sotamiesten rääkkäämänä heitettiin Jugurtha vankihuoneesen, jossa hän muutamien vuorokausien kuluttua menehtyi nälkäkuolemaan.
Sallustion kertomus Katilinan salaliitosta alkaa huomautuksella, että jokaisella ihmisellä, joka pyrkii kohoomaan muita luotuja olentoja ylemmäksi, on velvollisuutena koettaa elää toisella tavoin kuin elukat, ja pitää ajatusmahdin kunniaa ruumiillista voimaa parempana. Lyhyesti kuvattuaan Katilinan rohkeata, kunnianhimoista luonnetta, puhuu hän Roman perustajain avuista, ja huomauttaa sitäkin, että Athenalaisten urotekoja ylistettiin koko maailmassa mitä mainehikkaimpina sankartöinä, ja siitä tuli kiittää Kreikan suuria kirjailijoita, kun Romalaisilla sitä vastoin lahjakkaat miehet mieluummin toimivat kuin puhuivat ansioistaan. Hän osoittaa Roman kansan nyt suvustaan huonontuneen ja esittää, kuinka helposti Katilina, saituuden ja siveellisen turmion hävitettyä kaikki perusaatteet, saattoi niiden joukosta, jotka olivat tuhlanneet perityn omaisuutensa pelissä ja kalleissa nautinnoissa, koota ympärilleen kunniasta huolimattoman liittolaisjoukon, johon kuului muutamia senaattorejakin ja monta nuorta jalosukuista miestä. Sellaisten toverien avulla päätti hän kumota hallituksen, jo ennen otettuaan osaa tuumaan murhata useimmat senaattorit. Kun hänen ensimmäinen yrityksensä päästä konsuliksi oli rauennut tyhjiin, keksi hän uusia tuumia sekä Roman että koko Italiankin suhteen; niihin kuului myös yritys murhata Cicero, joka hänen sijaansa oli valittu konsuliksi. Vihdoin viimeinkin päätti hän panna toimeen julkisen kapinan. Eräs hänen liittoveljiään, Manlius, koetti Etruriassa yllyttää rahvasta ja ympärilleen koota rosvoja kaikenlaisia.
Nyt puhuttiin jo yleisesti salaliitosta, ja senaatti päätti, että "konsulien tulisi varoa, ettei valtio kärsisi mitään vahinkoa". Sanoma tuotiin Manlion ruvenneen taisteluun, ja puhuttiin ennusmerkeistä ja enteistä, vieläpä orjien kapinahankkeistakin. Vaaran suuruuden mukainen väennosto tehtiin, levottomuus painoi kaikkien mieliä, kamala kauhistus valtasi kaikki kansanluokat ja naiset kohottelivat rukoillen käsiänsä taivasta kohden.