Мало сведений и о том, как протекала его жизнь после подавления восстания Спартака. Видимо, в это время он оставался сугубо частным человеком. Даже его риторические упражнения оставались в значительной степени неизвестными широкой публике. Возможно, к этому времени относится его единственное публичное выступление. Когда народные трибуны задумали снести или передвинуть одну колонну в Порциевой базилике, в свое время построенной его прадедом, Катон счел это намерение оскорблением своего рода и решительно выступил против него. И на форуме перед собравшимся народом он произнес свою первую публичную речь, проявив в ней недюжинные ораторские способности. Катон выиграл дело и вновь удалился в частную жизнь.
К этому времени относится и его женитьба, которая, однако, сопровождалась неожиданным скандалом. Решив жениться, Катон с присущим ему рационализмом выбрал себе невестой Лепиду, которая была уже помолвлена со Сципионом Метеллом, но тот по какой-то причине расторг помолвку. И тогда Катон выступил претендентом на ее руку, явно желая породниться со знатной семьей Лепидов. Однако почти накануне свадьбы Метелл передумал и отнял у Катона невесту. Возмущению несостоявшегося жениха не было предела, он даже хотел подать в суд на Метелла, но был остановлен друзьями, убедившими его в том, что в таком случае он сам станет объектом насмешек. Отказавшись от судебной тяжбы, Катон обратился к поэзии и, подражая древнему греческому поэту Архилоху, излил в стихах весь свой гнев и обиду. Успокоившись и вернувшись к обычному образу жизни, Катон посватался к Атилии, дочери ничем не выдающегося Атилия Серрана, и вскоре женился на ней. Позже Атилия родила ему сына Марка и дочь Порцию.
Вскоре Катон решил стать военным трибуном, поскольку без военной ступеньки трудно было рассчитывать и на гражданскую карьеру. Официально эта должность была выборной, и Катон смело пошел на выборы. Более того, он демонстративно подчинялся недавно принятому закону, запрещавшему использовать услуги рабов-номеклаторов, которые при обходе кандидатом граждан называли своему хозяину их имена. Катон сам приветствовал всех встречных, что вызывало недовольство в том кругу, в котором он обычно вращался. Такое подчеркнутое повиновение закону в этом кругу воспринималось как своеобразный вызов. Катон был избран, и в 67 г. до н. э. отправился в Македонию к пропретору этой провинции Рубрию. Обычно молодых аристократов, отправлявшихся на службу в провинцию, сопровождал огромный штат из рабов, отпущенников, друзей или клиентов, предназначенный для того, чтобы сделать жизнь своего хозяина или патрона как можно легче и приятней. Катон же взял с собой всего пятнадцать рабов, двух отпущенников и четырех друзей, одним из которых был его лучший друг Мунаций Руф, которого юная супруга Катона умоляла позаботиться об ее муже. Мунаций обещал, но было неизвестно, кто о ком больше заботился — Мунаций о Катоне или Катон о Мунации.
Рубрий назначил Катона командиром одного из своих легионов и поручил ему контроль над районом Пропонтиды (Мраморное море), моря, входившего в систему проливов, соединяющих Понт Эвксинский и Эгейское море. Контроль над этим районом был очень важен для бесперебойного снабжения Рима и Италии северочерноморским хлебом. Вероятно, дисциплина у солдат, стоявших в столь отдаленном уголке Римской республики, изрядно расшаталась, раз Катону пришлось принимать значительные меры для ее восстановления. Действуя приказами и убеждениями, наставлениями и личным примером, он сумел не только восстановить дисциплину и боеспособность своего легиона, но и стать любимцем воинов, что в то смутное время было далеко не просто, тем более что никаких военных подвигов за Катоном не числилось.