Службу Сулла начал несколько позже, чем другие (следовавшие cursus honorum начинающие политики) — квестором в 107 году, подчиняясь консулу Гаю Марию[17][18]. Гай Марий должен был отправиться в Африку, где Рим завяз в Югуртинской войне в Нумидии против царя Югурты (начавшейся в 112 году и возобновившейся в 110 году). Сулла в этой войне должен был сопровождать Мария. Существует предположение, что Сулла получил должность квестора и командование в войне благодаря женитьбе на родственнице Гая Мария[19]. Отмечается также, что Сулла мог выбрать Мария из двух полководцев, к которым можно было присоединиться (вторым был Луций Кассий Лонгин, вскоре разгромленный германцами[19]). Первым заданием Суллы был сбор в Италии значительного вспомогательного конного войска и переброска его в Северную Африку[15]. Сулле потребовалось лишь несколько месяцев, чтобы справиться с этим и зарекомендовать себя с самой лучшей стороны. Вскоре Луцию удалось завоевать уважение воинов благодаря умелому руководству войсками в столь юном возрасте, хотя, возможно, причиной тому было его обаяние[20].