Считается, что его предок Сергест приплыл в Италию вместе с Энеем с востока после Троянской войны, в то время, когда Рима как города еще не существовало. Среди его родни голубых кровей был герой войны с Ганнибалом, его прадед, который прославился как первый воин, сражавшийся с протезом вместо руки, — скорее всего, это был просто металлический крюк, заменивший правую кисть, потерянную в предыдущих боях. У самого Катилины политическая карьера начиналась вполне успешно, его избирали на несколько младших должностей, но к 63 г. до н.э. он почти обанкротился. Его имя было прочно связано с серией преступлений: от убийства первой жены и собственного сына до сожительства с весталкой, хранившей обет безбрачия. Помимо разорительных пороков его финансовое положение расшатали неоднократные попытки обеспечить себе самую влиятельную в городе должность одного из двух консулов.