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