W 66 p.n.e. Celer służył jako legat Pompejusza na Wschodzie, uczestnicząc w walkach z królem Armenii Tigranesem. Wojska Pompejusza spędzały zimę podzielone na trzy części. Obóz, którym dowodził Celer został zaatakowany przez Oroesesa, króla Albanów, mieszkających poza rzeką Cyrnus. Celer zdecydowanie odparł atak AlbanówKasjusz Dion Kokcejanus, Historia rzymska, Księga XXXVI.. W 63 p.n.e. został pretorem. Doszło wtedy do procesu, w którym Tytus Labienus, zaskarżył Gajusza Rabiriusza za zabicie Saturninusa (sprawa dotyczyła wydarzeń sprzed trzydziestu sześciu lat, gdy walkę z Saturninem zlecił senat ówczesnym konsulom). Proces doprowadził do burzliwych starć i sporów. Dzięki postawie Cezara doszło do skazania Rabiriusza. Rabiriusz zgłosił apelację, ale i tak lud uznałby go winnym, gdyby nie zapobiegł temu Metellus Celer, doprowadzając do zerwania zgromadzenia (komicja centurialne)Kasjusz Dion Kokcejanus, Historia rzymska, Księga XXXVII.. Był to też rok walki ze sprzysiężeniem Katyliny. Celer zbierał wojska przeciw niemu w Picenum i Galii.