카틸리나는 기원전 108년 유서깊은 귀족가문에서 태어났다. 선대에 집정관을 지낸 집안이었으나 그의 시대에는 경제적으로나 정치적으로 쇠퇴해가는 가문이었다. 카틸리나는 군사적 재능을 보여 동맹시 전쟁당시 폼페이우스 스트라보의 밑에서 키케로, 폼페이우스와 함께 참전했다. 가이우스 마리우스의 시절에 별다른 역할을 하진 않았지만 정치적으로 실각하진 않았고 술라 내전 시기에는 술라의 편에 섰다. 기원전 73년 로마 신전의 여사제와 간통혐의를 받았으나 퀸투스 루타티우스 카툴루스의 도움으로 무죄가 되었다.

기원전 68년 법무관이 되었고 그 다음 2년간은 아프리카 속주의 총독으로 있었다. 로마로 돌아와서 기원전 65년 겨울 집정관직에 출마하려 했으나 속주민 대표단이 그를 권력남용으로 원로원에 기소하여 재판에 회부되는 바람에 입후보 자격을 상실했다. 그 불만으로 음모를 꾀했으나 실패하였다(제1차 카틸리나 음모 사건). 수많은 로마의 유력자들의 지원으로 무죄가 선고되었으나 집정관직은 놓쳤다. 다음해에도 집정관직을 노리고 출마했으나 원로원의 지원을 받은 키케로와 가이우스 안토니우스가 당선되는 바람에 좌절했다. 당시 그는 부채의 전액 탕감을 공약으로 내걸었는데 그런 급진적인 공약을 두려워한 원로원은 그를 방해했다.
카틸리나는 누구 덕분에 간통 혐의에서 벗어날 수 있었나요?
퀸투스 루타티우스 카툴루스