在公元前104年，曾多次击败罗马军团的两个日耳曼部落——金布里和条顿人似乎再次准备进军意大利。
此时正值军事危机之际，盖乌斯·马略寻求并获得了连续多次的执政官职位，这一举动引起了元老院中贵族的不满。
然而，他们可能也承认了马略在击败日耳曼入侵者中的军事才能不可或缺。
在重新调整政治联盟的过程中，元老院中的传统派推举了身为贫困贵族的苏拉，以对抗新崛起的马略。
从公元前104年开始，马略在南高卢对战败的罗马军队进行改革。
苏拉作为其昔日指挥官的副将，在这一职位上成功镇压了一个因罗马此前的失败而叛乱的高卢部落。
次年，苏拉被选为军事护民官，并在马略手下效力。
他被指派与日耳曼入侵者之一的马尔西人（marsi）谈判，并成功说服他们脱离金布里和条顿人。
然而，由于马略没有给他提供更高的晋升机会，苏拉开始“极不公正”地抱怨马略剥夺了他的机会。
于是他要求调任到马略的执政官同僚卡图卢斯（catulus）的军队，并获得批准。
公元前102年，入侵者再次来袭，试图越过阿尔卑斯山。
卡图卢斯和苏拉一同前往阻挡他们的前进，两人可能配合得很好。
但卡图卢斯的军队在东部阿尔卑斯被击败，撤退到威尼托（Venetia），随后退至波河（po）南岸。
同时，马略在阿奎塞克斯蒂亚战役（battle of Aquae Sextiae）中彻底歼灭了金布里的盟友条顿人。
马略再次当选为公元前101年的执政官，并前往援助卡图卢斯。
苏拉负责后勤保障，他出色地完成了任务，确保两军的粮食供给充足。
随后，两军越过波河，向金布里发起进攻。
在谈判失败后，罗马人与金布里在拉乌迪安战场（Raudian Field）交战，金布里最终被击溃和消灭。
胜利后，作为指挥官的马略和卡图卢斯都获得了凯旋式的荣誉。
苏拉拒绝竞选财务官职，该职位因涉及举办公共游戏而极为昂贵。
在古罗马，财务官职位的职责之一是组织和资助公共娱乐活动，如竞技表演、角斗比赛和节庆。
这些活动对罗马市民来说非常重要，且通常规模宏大。
因此，竞选财务官的人往往会用自己的资金举办这些公共游戏，以赢得民众的好感和支持，从而为他们的政治生涯加分。
苏拉转而在公元前99年成为执政官的候选人，然而，他在这次竞选中失败了。
在后来的回忆录中，通过普鲁塔克的记述，苏拉宣称他的失败是因为民众要求他先担任财务官，以便他能利用与博库斯（bocchus）的友谊（博库斯是一位富有的君主）来筹措资金举办比赛。
尽管这一故事的真实性存疑，但苏拉在次年再次参选执政官，并承诺会提供精彩的表演，成功当选为公元前97年的城市执政官。
---
他的执政官任期算是平淡无奇，除了与盖乌斯·尤利乌斯·凯撒·斯特拉波（Gaius Julius caesar Strabo，可能是他的连襟）的公开争执，以及盛大地举办了阿波罗竞技会。
第二年，即公元前96年，他以代理执政的身份被派往小亚细亚的基利基亚（cilicia）。
在治理基利基亚时，苏拉接到元老院的命令，恢复阿里奥巴扎内斯（Ariobarzanes）为卡帕多西亚的国王。
阿里奥巴扎内斯被本都（pontus）的米特里达梯六世（mithridates VI）驱逐，后者试图将其一子阿里阿拉塞斯（Ariarathes）安插在卡帕多西亚的王位上。
尽管起初遇到困难，苏拉却在缺乏资源和准备的情况下成功达成了任务。
他迅速征募盟军，带领少量罗马士兵快速推进至崎岖地带，并击溃了数量占优的敌军。苏拉的领导才能使他的士兵印象深刻，士兵们称他为“大元帅”（imperator）。
苏拉在卡帕多西亚的战役使他来到了幼发拉底河（Euphrates）河畔，在那里他遇到了帕提亚帝国（parthian Empire）派来的使节团。
苏拉成为首位接待帕提亚使节的罗马官员。
会面时，他坐在帕提亚使节奥罗巴佐斯（orobazus）与阿里奥巴扎内斯之间，意图通过这种安排在心理上压倒帕提亚使节，暗示帕提亚和卡帕多西亚地位相等，而罗马则居于上位。
奥罗巴佐斯在返回帕提亚后被处决，原因是允许这种屈辱外交发生。
尽管如此，帕提亚仍然批准了此次达成的协议，将幼发拉底河确立为帕提亚与罗马之间的明确边界。
在此次会面中，有一位迦勒底的占星师告诉苏拉，他将会在声望与财富的巅峰时期去世。
这个预言在苏拉的一生中产生了深远的影响。
在公元前94年，苏拉将亚美尼亚（Armenia）大帝提格兰（tigranes the Great）的军队击退出卡帕多西亚。
据推测他在东方停留至公元前92年，当年返回罗马。
凯维尼（Keaveney）则认为他在公元前93年离开东方。
苏拉在东方的成就广受赞誉：他恢复了阿里奥巴扎内斯的王位，获得了军队的“大元帅”称号，并成为首位成功与帕提亚会晤的罗马人。
凭借军事和外交的双重胜利，他的政治前景似乎十分光明。
然而，当他被指控敲诈阿里奥巴扎内斯时，他的候选人资格受到了打击。
尽管检控官在审判当日未出庭，使得苏拉自动胜诉，但他的政治抱负受到了挫折。
---
公元前91年到公元前87年，意大利发生了同盟战争。
罗马与其盟友的关系在公元前91年之前的数年中逐渐恶化。
从公元前133年提比略·格拉古（tiberius Gracchus）开始推行土地改革起，意大利的社区被逐渐驱逐出实际属于罗马的公共土地，这些土地世代以来并没有严格的所有权管理。
几十年来，各种给予盟友罗马公民权的提案因各种原因均未能通过，而盟友们也“逐渐认识到不应再作为罗马的附庸，而是应通过获得公民权来共同行使帝国的权力”。
金布里战争（cimbric war）期间，罗马颁布的反贪腐法律允许盟友提出敲诈指控，进一步激发了意大利各地的团结意识。
当亲意大利派的平民保民官马库斯·李维乌斯·德鲁苏斯（marcus Livius drusus）在公元前91年被暗杀，他当时正试图再次通过一项给予罗马公民权的法案，这一事件激起了意大利各地的反叛。
同年，博库斯（bocchus）资助建造了一座雕像，展示了苏拉俘获朱古达的场景。
这可能与苏拉竞选执政官有关。
无论如何，如果他当时确实有竞选执政官的打算，战争的爆发使这一计划被搁置。
战争初期，战斗主要集中在两个战区：
北部战区从皮切努姆（picenum）延伸至富奇内湖（Fucine Lake），南部战区则包括萨姆尼乌姆（Samnium）。
苏拉在南部战区担任执政官卢基乌斯·尤利乌斯·凯撒（Lucius Julius caesar）的副将之一。
在战争的第一年，罗马的战略主要是围堵，试图阻止反叛的盟友将叛乱扩展到罗马控制的领土。
苏拉在意大利南部，主要在卢基乌斯·尤利乌斯·凯撒的侧翼采取防御策略，而凯撒则进行进攻性作战。
年末时，苏拉与北部战区的马略在意大利南部北部地区配合作战，击败了马尔西人（marsi）。
马略击败了马尔西人，将他们驱赶至苏拉的伏击圈中。
苏拉还试图协助卢基乌斯解救被围的埃塞尼亚（Aesernia），但两人均未能成功。
次年，即公元前89年，苏拉在执政官卢基乌斯·波尔修斯·卡托（Lucius porcius cato）麾下担任副将。
但卡托在与马尔西人的战斗中阵亡，苏拉以代理执政官的身份继续留任，并获得了南部战区的最高指挥权。
他对庞贝城（pompeii）发起围攻。
在另一位副将被其部下杀害后，苏拉拒绝对士兵进行惩罚，仅发布公告敦促他们在面对敌人时表现得更勇敢。
在围攻庞贝城期间，一支由卢基乌斯·克伦提乌斯（Lucius cluentius）率领的意大利援军试图解围，苏拉击败了他们，并将其驱赶至诺拉（Nola）。
在诺拉城墙下击杀克伦提乌斯后，苏拉继续围困该城，并因其功绩获得了草冠（grass crown），这是罗马军队的最高军事荣誉。
庞贝城在该年某个时候被攻占，随后是斯塔比亚（Stabiae）和埃克拉努姆（Aeclanum）。
在攻占埃克拉努姆后，苏拉迫使赫尔皮尼人（hirpini）投降。
他随后进攻萨姆尼特人（Samnites），并在埃塞尼亚附近击溃了他们的一支军队，随后攻占了新的意大利首都博维安乌姆·乌恩德西马诺鲁姆（bovianum Undecimanorum）。
所有这些胜利应在公元前89年10月的执政官选举前完成。
罗马的政治发展也开始推动战争的结束。
公元前89年，一位平民保民官通过了《普劳提亚·帕皮里亚法》，赋予所有盟友公民权（仍在战斗中的萨姆尼特人和卢坎尼亚人除外）。
此前，卢基乌斯·尤利乌斯·凯撒于公元前90年10月通过的《尤利亚法》已赋予忠诚的盟友以公民权。
在击败罗马的传统敌人萨姆尼特人并取得意大利各地的胜利后，苏拉竞选公元前88年执政官，并轻松当选，其同僚为昆图斯·庞培·鲁弗斯（quintus pompeius Rufus）。