590年，隋文帝杨坚因平定了陈国，让太子少保兼纳言苏威作《五教》颁布民间，命令无论长幼都要诵读。为此士民颇有怨言，再加上民间谣传大隋要把江南士民迁徙到关中去，导致江南士民人人惊慌。 于是婺州汪文进、越州高智慧、苏州沈玄侩等人举起了反隋的大旗，自称天子，设置百官，还有乐安蔡道人、蒋山李稜、温州沈孝彻、饶州吴世华、泉州王国庆、杭州杨宝英、交州李春等人也自称大都督，纷纷起兵攻陷州县，大肆杀戮州县官，原陈国的属地差不多都反了。
隋文帝杨坚诏命内史令杨素为行军总管，率军讨平叛乱。杨素部下子总管来护儿建议出奇兵偷渡过江，直捣贼营，杨素认为可行，便与来护儿率领数百轻舟登岸，火烧贼营。叛军大败，高智慧逃命入海，杨素率军追到海上，顺便平定了王文进、蔡道人、沈孝彻。
杨素派遣总管史万岁帅两千士卒追击叛贼。史万岁从婺州寻路翻山过海，一路奋勇向前，攻破敌洞不计其数，三个多月时间，前后有七百多场厮杀，转战一千余里，众人都以为史万岁全军覆没了，不料意外获得了他用竹筒漂来的书信。杨素把情况上奏，隋文帝感到很惊讶，如此骁勇善战的将领实属难得，因而大加赏赐史万岁十万钱，拜左领军将军，加封太平公。
隋文帝杨坚
到了597年，又有南宁州羌族首领爨玩背叛隋廷。爨玩是隋朝初年来降，朝廷为他主动投顺，加授他为昆州刺史。只是羌蛮叛服无常，爨玩仗着地势偏远，讨伐他不那么容易，因此大着胆子做起乱来。 隋文帝再派史万岁担任行军总管，率领大军讨伐。史万岁帅军从蜻蛉川到南中，一路过关捣穴，经过诸葛亮纪功碑，渡西洱河，再入渠滥川，军行一千多里，击破三十多个羌部，俘虏两万多人。 史万岁上奏，要将爨玩押解朝廷，但爨玩怀着贰心，不想进京，就用金宝贿赂史万岁，史万岁财迷心窍，竟然就把这个费劲吧啦逮住的羌酋轻而易举的放了，自己率军回了京。
过了年余，爨玩果然又整顿兵马闹腾起来，蜀王杨秀上奏说史万岁接受贿赂放走了叛贼，才导致边境发生祸乱。史万岁在隋文帝面前不承认受贿之事，恼得隋文帝大发雷霆，下令斩了史万岁，幸亏尚书左仆射高颎与左卫大将军元旻等人极力为他求情，隋文帝才饶他一命，把他除名为民。
史万岁画像
不过史万岁闲居没多久，就因为突厥达头入侵而被起用。当时突厥都蓝可汗被部下所杀，达头自立为步迦可汗，国内大乱。达头要证明自己的实力，把矛盾的焦点向外转移，因此向隋朝边境发起进攻。隋文帝下诏命令晋王杨广与越国公杨素从灵武道出击，汉王杨谅与太平公史万岁出马邑道迎击达头。史万岁率军走到大斤山，与达头遭遇，达头派使者问隋将是谁？侦查兵报说是史万岁。达头问:“莫非是那个敦煌庶卒吗？”侦察兵答:“是。”达头废话不多说，吓得招呼部下打马而逃。
达头所说的“敦煌戍卒”，是指开皇二年大将军史万岁因罪被发配到敦煌做戍卒，当时秦州总管窦荣定率三万步骑兵，与突厥阿波可汗在高越原交战，史万岁跑到窦荣定军前自请效力，窦荣定非常高兴，就派人向阿波可汗提议各派一名壮士决一胜负，阿波可汗同意了，派出一名骑将来挑战，窦荣定就派史万岁出阵应战，史万岁骁勇，以迅雷不及掩耳之势抢到突厥骑将面前，乘其不备斩下他的头颅奔回军中。突厥大惊，不敢再战，请求结盟之后率军退去。 阿波可汗与达头是叔侄关系，因此史万岁的威名，达头可汗也有所耳闻。听说这次又是史万岁帅兵来战，直接就吓跑了，史万岁追出一百多里，大败突厥，斩杀突厥一千多人。
史万岁战突厥
史万岁从大斤山回京以后，杨素妒忌他的功劳，在隋文帝面前进言说：“突厥已经投降了，他们本来不是入寇，只是到边境放牧而已。”史万岁数次上表陈述，隋文帝仍未醒悟。此时，隋文帝刚废掉太子杨勇，正追查东宫的党羽。隋文帝问史万岁在何处，史万岁当时确实在朝堂上，杨素想激怒隋文帝，就故意僭毁说：“史万岁拜见东宫去了。”隋文帝信以为真，便下令召见史万岁。 当时出征将士数百人在朝堂呼冤，史万岁对众人说：“我今日将把你们的功劳陈述给皇上，事情应当有所决断。”史万岁见到隋文帝后，说：“将士有功，却被朝廷所抑制！”说的言辞激愤，隋文帝晚年本就易怒，听了史万岁的申诉，不觉大动肝火，下令左右扑杀他，左右拖下去后，隋文帝又后悔了，派人去追，但已经迟了，隋文帝顾及尊严，只得下诏宣告史万岁的罪状，天下之人无不为史万岁感到惋惜。
杨素画像
