杨坚专政。六月相州(今河北省临漳西南邺镇)总管尉迟迥(北周帝宇恭外甥)恐杨坚专权对北周不利公开起兵反对杨坚。史万岁随行军总管梁士彦前往征讨。军至冯翊(今陕西大荔县)有群雁飞来史万岁对梁士彦说：“射行中第三者”(《隋书·史万岁列传》)。于是发弓射去雁应弦而落。三军见史万岁射技如此高超无不心悦诚服。军至河北与尉迟迥军相遇史万岁每战先登勇冠三军。邺城(今河北省临漳西南)之战官军初战不利稍稍退却情势十分危急史万岁大呼：“事急矣吾当破之”(《隋书·史万岁列传》)。于是身先士卒驰马奋击连击数十人。在众人的协助政官军士气复振迅速扭转了战局。平叛后史万岁因功拜为将军。数年后史万岁因大将军尔朱绩谋反被杀而受牵连发配敦煌(今甘肃敦煌西)为戍卒。敦煌戍主甚勇武常单骑深入突厥掠取羊马突厥无论众寡都莫之敢当。因此戍主颇自负常辱骂史万岁。史万岁非常忧虑于是自言也精于骑射。戍主令其驰射见果有功底笑着说：“小人定可”(《隋书·史万岁列传》)。史万岁又单骑驰马入突厥境内夺取六畜而归。戍主这才改变了对史万岁的态度常与他同行深入突厥境数百里名振北夷。时隋帝为完成统一大业正与突厥作战。隋在抗御突厥进攻的同时已完成了反击准备。隋开皇三年(583年)四月隋军发起全面反击。隋帝杨坚命秦州总管窦荣定率9总管、步骑兵3万由凉州(治今甘肃武威)道北击突厥。五月二十四日与突厥阿波可汗所部在高越原(今甘肃民勤西北)地区相拒。高越原地处沙漠地带干枯无水。窦荣定军刺马血解渴；死者十分之二三。忽然遇雨隋军士气大振。窦荣定乘势挥军奋力冲击多次挫败阿波军。史万岁此时自投军门求报效要求立功赎罪。窦荣定数闻其骁勇便于二十五日派人向突厥提出：“士卒何罪过令杀之但当各遣一壮士决胜负耳”(《隋书·史万岁列传》)。阿波可汗应允遂派一名骑将挑战窦荣定派万岁出马应战万岁驰斩其将而还。突厥大惊不敢再战即议和而退。了因此被授仪同兼车骑将军。隋开皇九年(589年)因参加隋灭陈之战有功加开府。江南自东晋以来世家士族一直欺压寒门庶族。隋灭陈统一中国后南方士族豪强因对隋实行的限制政策不满便利用民间对隋欲移民关中流言的惊恐心理乘机煽动叛乱。隋开皇十年十一月婺州(治今浙江金华)汪进、越州(治今浙江绍兴)高智慧、苏州沈玄侩等均举兵反隋自称天子署置百官起兵攻陷州县反乱大抵遍及原陈属地。其规模大者数万人小者数千人互相呼应残杀隋朝官吏。隋帝杨坚命内史令杨素为行军总管率军平叛。杨素初败高智慧后即派史万岁(时为行军总管)率军2000人进攻婺州杨素则率主力由海道追击逃入海中的高智慧直趋温州。史万岁率军从东阳(今浙江省中部金华江游)别道而进平定蔡道人、汪进翻岭越海转战千余里历经700多次战斗击败叛军无数。史万岁军数十日杳无音信远近皆以为其部已全军。由于水陆交通阻绝信使不通史万岁只得置书信于竹筒之中浮于水顺流而下。有取水之人得到竹筒后报告给杨素。杨素大喜并奏报于隋帝。隋帝接报后赞叹不已赐史万岁家钱十万官拜左领军将军。杨素军也继续追击反隋散兵抓获高智慧平定了叛乱。南宁州(治味县今云南曲靖西)羌族首领爨翫于隋初接受招抚被任命为昆州(治在今云南昆明市西郊马街附近)刺史后又叛隋。隋开皇十七年(597年)二月隋帝史万岁为行军总管击爨翫。史万岁率部经蜻蛉川(今云南大姚)、弄栋(今云南姚安北)、小勃弄、大勃弄(二地均在今云南下关东南)进入南宁州地区。爨翫依险固守均被史万岁击破。隋军行数百里经过诸葛亮纪功碑见其背刻铭：“万岁之后胜我者过此”(《隋书·史万岁列传》)。史万岁令左右将碑倒置继续向西挺进渡西洱河(今云南洱海)入渠滥川(位于云南下关东北)转战千余里破西南羌族30余部俘2万余人诸羌大惧爨翫被迫再度降。献明珠宝物表示愿听约束并刻石勒铭赞颂隋朝圣德。史万岁遣使飞骑奏将爨翫入朝隋帝准其所奏。但爨翫心怀二志不想随军入朝便以金宝贿赂史万岁于是史万岁便放爨翫而还。当时蜀王杨秀正在益州(今四川省成都)知其受贿派人索取。史万岁闻知此事将所得金宝全部沉于江底杨秀无所获只得作罢。史万岁以平定南方各部落之功位进柱国又因与晋王杨广友善而兼督晋王府军事。第二年爨翫又反叛。蜀王杨秀弹劾史万岁受贿纵贼致生边患毫无大臣气节。隋帝下令严查此事查对属实其罪当死。隋帝责问他：“受金放贼重劳士马。朕念将士暴露寝不安席食不甘味卿岂社稷臣也？”史万岁辩解说：“臣留爨翫者恐其州有变留以镇抚。臣还至泸水诏书方到由是不将入朝实不受赂。”隋帝见史万岁心有欺隐大怒道：“朕以卿为好人何乃官高禄重翻为国贼也？”并对有司说：“明日将斩之”(《隋书·史万岁列传》)。史万岁惧而服罪向隋帝顿首命。左仆射高颎和左卫大将军元旻等见他已认罪便也为他说情：“史万岁雄略过人每行兵用师之处未尝不身先士卒尤善抚御将士乐为致力虽古名将未能过也”(《隋书·史万岁列传》)。隋帝听后怒气稍解将他削官为民。一年后恢复官爵授河州(今甘肃省临夏东北)刺史兼领行军总管以防备胡人来犯。隋开皇十九年(599年)突厥都兰可汗被部下所杀其部落大乱。为挽救突厥颓势达头可汗自立为步迦可汗于开皇二十年(600年)四月率兵进犯隋边。隋帝命晋王杨广、尚书右仆射杨素出灵州(治回乐今宁夏灵武西南)汉王杨谅与史万岁出朔州(治善阳今山西朔县)合击步迦可汗。史万岁率柱国张定和、大将军李药王、杨义臣出塞军至大斤山(即今内蒙大青山)与步迦可汗军遭遇。步迦可汗派人问：“隋将为谁？”侦察骑兵报告说：“史万岁也。”步迦可汗又问：“得非敦煌戍卒乎？”侦察骑兵说：“是也”(《隋书·史万岁列传》)。步迦确定隋军统兵将帅是当年威震敦煌的史万岁后慌忙引军回撤。史万岁挥马追击百余里大破突厥军斩杀数千。又继续跟踪追入沙漠数百里凯旋而归。史万岁自大斤山回京后杨素妒忌其功在隋帝面前谮言史万岁说：“突厥本降初不为寇来于塞畜牧耳”(《隋书·史万岁列传》)。遂埋没其功不予褒奖。史万岁数次表陈述隋帝仍未醒悟。此时隋帝从仁寿宫初还京师并刚废掉太子杨勇所以严防东宫结党谋变。隋帝问史万岁现在何处其时史万岁正在朝堂但杨素见隋帝正怒却故意说：“万岁谒东宫矣”(《隋书·史万岁列传》)。以激怒隋帝。隋帝果然信以为真立即下令召见史万岁。当时出征将士数百人在朝称冤史万岁对众人说：“吾今日为汝极言于事当决矣”(《隋书·史万岁列传》)。史万岁见到隋帝后说：“将士有功为朝廷所抑”(《资治通鉴·卷第一百七十九》)！言辞愤激有忤于。杨坚越发震怒令武士将史万岁暴杀于朝堂。既而后悔但已追之不及。只好下诏加罪于史万岁：“柱国、太平公万岁拔擢委任每总戎机。往以南宁逆乱令其出讨。而昆州刺史爨玩包藏逆心为民兴患。朕备有