Смерть Юлии стала потрясением для родителей и самого Помпея, который хотел похоронить её в своём поместье, однако римляне убедили его похоронить Юлию на Марсовом поле. После смерти Юлии Помпей отказался от повторного союза с семьёй Цезаря в пользу Красса.

Он женился в пятый раз на Корнелии Метелле, вдове погибшего в парфянском походе Публия Красса и одновременно дальней родственнице Марка Красса. Несмотря на политический характер женитьбы, этот брак считался счастливым, хотя в Риме порицалось неравенство в возрасте, Корнелия была намного моложе своего мужа. Как и Юлия, она разбиралась в науках, искусствах, покровительствовала им.

В 58 году до н. э. Антоний покинул Рим и отправился в Грецию. Этому способствовали, во-первых, ссора с Клодием из-за Фульвии, во-вторых, давление кредиторов, в-третьих, желание Марка улучшить своё ораторское мастерство, что было важно для успешной политической карьеры в Римской республике. В публичных выступлениях он пытался ориентироваться на пышный и изысканный стиль.

В том же году Марк, которому всего 25 лет, принял предложение консула Авла Габиния о службе под его началом в Сирии. Габиний решил взять с собой известного представителя «золотой молодёжи» без опыта руководства войсками, лишь учитывая связи двух родов в прошлом. Дед Авла служил под началом деда Марка в Киликии в 102 году до н. э.

Антоний сразу потребовал важную должность – место префекта кавалерии, под командованием которого находились один или несколько отрядов по 400—500 кавалеристов каждый. Перед новым наместником Сирии, помимо обычного разбора дел в провинции, стояла также задача восстановить римское влияние в Иудее, где сын свергнутого царя попытался свергнуть римского ставленника. Во время штурма крепости, опоры мятежного принца, Антоний первым поднялся на стену, заслужив почётную воинскую награду. Марк участвовал во взятии других важных крепостей мятежников.

Габиний готовился напасть на Парфию, когда к нему обратился изгнанный из Египта фараон Птолемей XII Авлет и переменил все планы полководца. В 59 году до н. э. изгнанный из Египта фараон Птолемей XII Авлет заплатил триумвирам и лично Цезарю огромную взятку за признание своей власти и за признание себя «другом и союзником римского народа».

«Друг и союзник римского народа» не являлся слугой и рабом, тем самым Рим отказывался от претензий на владение Египтом. В следующем 58 году до н. э. Птолемея свергли в пользу его дочери Береники, он вновь попросил у Рима поддержку. Сенаторы отказали фараону. После неудачи в Риме Птолемей обратился напрямую к Габинию, пообещав ему огромную взятку в 10 тысяч талантов за использование римской армии для своего восстановления на троне.

После некоторых раздумий Авл Габиний согласился, хотя и знал про изданный в Риме религиозный запрет. По закону наместник не мог покидать свою провинцию и вторгаться в другие земли без специального разрешения сената или народного собрания. Антоний последовал за наместником, хотя многие другие офицеры отказались ввязываться в нелегальное предприятие.

Во время беспорядков 58—55 гг. до н. э. Птолемей XII был свергнут и изгнан из Египта, царицей стала его старшая дочь Береника. Восстановленный на престоле силами римского наместника Сирии Габиния, Птолемей XII устраивает резню, репрессии и убийства, жертвой которых пала и Береника. Птолемей XII Авлет удерживался у власти лишь благодаря римскому присутствию, что сильно сказывалось и обременяло финансы Египта.

Осенью 56 года до н. э. Габиний обвинил египетские власти в покровительстве пиратам и в подготовке мощного флота, создававшего угрозу римскому господству на море. Под этим предлогом он ввёл свои войска в Египет. Антонию поручалась важная задача по захвату стратегически важного пункта, через который лежал путь на Александрию. Кавалерия Марка быстро прошла через пустыни Синая и солёные заболоченные лагуны Суэцкого перешейка.