史萬歲京兆杜陵(今陝西西安市東南)人，隋朝名將。
史萬歲的父親史靜，為北周滄州刺史。史萬歲「少英武，善騎射，驍捷若飛。好讀兵書，兼精占候」(《隋書-史萬歲列傳》)。北周保定四年(564年)，北周和北齊戰於洛陽城北之北邙山(今河南洛陽市北)。15歲的史萬歲隨父從軍，他觀察戰場形勢，認為周軍將敗，並令左右換裝離去。不久，周軍果然大敗，其父因此奇之。北周建德六年(577年)，周武帝宇文邕率軍平齊，其父史靜戰死，史萬歲以忠臣之子，拜開府儀同三司，襲爵為太平縣公。
北周大象二年(580年)五月，北周宣帝宇文贊病死。周靜帝宇文衍年幼，左丞相楊堅專政。六月，相州(今河北省臨漳西南鄴鎮)總管尉遲迥(北周文帝宇文恭外甥)恐楊堅專權對北周不利，公開起兵反對楊堅。史萬歲隨行軍總管梁士彥前往征討。軍至馮翊(今陝西大荔縣)，有群雁飛來，史萬歲對梁士彥說：「請射行中第三者」(《隋書-史萬歲列傳》)。於是發弓射去，雁應弦而落。三軍見史萬歲射技如此高超，無不心悅誠服。軍至河北，與尉遲迥軍相遇，史萬歲每戰先登，勇冠三軍。鄴城(今河北省臨漳西南)之戰，官軍初戰不利，稍稍退卻，情勢十分危急，史萬歲大呼：「事急矣，吾當破之」(《隋書-史萬歲列傳》)。於是身先士卒，馳馬奮擊，連擊數十人。在眾人的協助政，官軍士氣復振，迅速扭轉了戰局。平叛後，史萬歲因功拜為上將軍。
數年後，史萬歲因大將軍爾朱績謀反被殺而受牽連，發配敦煌(今甘肅敦煌西)為戍卒。敦煌戍主甚勇武，常單騎深入突厥掠取羊馬，突厥無論眾寡都莫之敢當。因此戍主頗自負，常辱罵史萬歲。史萬歲非常憂慮，於是自言也精於騎射。戍主令其馳射，見果有功底，笑著說：「小人定可」(《隋書-史萬歲列傳》)。史萬歲又單騎馳馬入突厥境內，奪取六畜而歸。戍主這才改變了對史萬歲的態度，常與他同行，深入突厥境數百里，名振北夷。
時隋文帝為完成統一大業，正與突厥作戰。隋在抗禦突厥進攻的同時，已完成了反擊準備。隋開皇三年(583年)四月，隋軍發起全面反擊。隋文帝楊堅命秦州總管竇榮定率9總管、步騎兵3萬，由涼州(治今甘肅武威)道北擊突厥。五月二十四日，與突厥阿波可汗所部在高越原(今甘肅民勤西北)地區相拒。高越原地處沙漠地帶，乾枯無水。竇榮定軍刺馬血解渴；死者十分之二三。忽然遇雨，隋軍士氣大振。竇榮定乘勢揮軍奮力衝擊，多次挫敗阿波軍。史萬歲此時自投軍門請求報效，要求立功贖罪。竇榮定數聞其驍勇，便於二十五日派人向突厥提出：「士卒何罪過，令殺之，但當各遣一壯士決勝負耳」(《隋書-史萬歲列傳》)。阿波可汗應允，遂派一名騎將挑戰，竇榮定派萬歲出馬應戰，萬歲馳斬其將而還。突厥大驚，不敢再戰，即請議和而退。了因此被授上儀同，兼車騎將軍。
隋開皇九年(589年)，因參加隋滅陳之戰有功，加上開府。
江南自東晉以來，世家士族一直欺壓寒門庶族。隋滅陳統一中國後，南方士族豪強因對隋實行的限制政策不滿，便利用民間對隋欲移民關中流言的驚恐心理，乘機煽動叛亂。隋開皇十年十一月，婺州(治今浙江金華)汪文進、越州(治今浙江紹興)高智慧、蘇州沈玄儈等均舉兵反隋，自稱天子，署置百官，起兵攻陷州縣，反亂大抵遍及原陳屬地。其規模大者數萬人，小者數千人，互相呼應，殘殺隋朝官吏。隋文帝楊堅命內史令楊素為行軍總管率軍平叛。
楊素初敗高智慧後，即派史萬歲(時為行軍總管)率軍2000人進攻婺州，楊素則率主力由海道追擊逃入海中的高智慧，直趨溫州。史萬歲率軍從東陽(今浙江省中部金華江上游)別道而進，平定蔡道人、汪文進，翻嶺越海，轉戰千餘里，歷經700多次戰鬥，擊敗叛軍無數。史萬歲軍數十日杳無音信，遠近皆以為其部已全軍。由於水陸交通阻絕，信使不通，史萬歲只得置書信於竹筒之中，浮於水上，順流而下。有取水之人得到竹筒後，報告給楊素。楊素大喜，並上奏報於隋文帝。隋文帝接報後讚歎不已，賜史萬歲家錢十萬，官拜左領軍將軍。楊素軍也繼續追擊反隋散兵，抓獲高智慧，平定了叛亂。
南寧州(治味縣，今雲南曲靖西)羌族首領爨翫於隋初接受招撫，被任命為昆州(治在今雲南昆明市西郊馬街附近)刺史，後又叛隋。隋開皇十七年(597年)二月，隋文帝史萬歲為行軍總管擊爨翫。史萬歲率部經蜻蛉川(今雲南大姚)、弄棟(今雲南姚安北)、小勃弄、大勃弄(二地均在今雲南下關東南)，進入南寧州地區。爨翫依險固守，均被史萬歲擊破。隋軍行數百里，經過諸葛亮紀功碑，見其背刻銘文：「萬歲之後，勝我者過此」(《隋書-史萬歲列傳》)。史萬歲令左右將碑倒置，繼續向西挺進，渡西洱河(今雲南洱海)，入渠濫川(位於雲南下關東北)，轉戰千餘里，破西南羌族30餘部，俘2萬餘人，諸羌大懼，爨翫被迫再度請降。獻明珠寶物，表示願聽約束，並刻石勒銘，讚頌隋朝聖德。史萬歲遣使飛騎上奏，請將爨翫入朝，隋文帝准其所奏。但爨翫心懷二志，不想隨軍入朝，便以金寶賄賂史萬歲，於是史萬歲便放爨翫而還。當時蜀王楊秀正在益州(今四川省成都)，知其受賄，派人索取。史萬歲聞知此事，將所得金寶全部沉於江底，楊秀無所獲，只得作罷。史萬歲以平定南方各部落之功，位進上柱國，又因與晉王楊廣友善，而兼督晉王府軍事。
第二年，爨翫又反叛。蜀王楊秀彈劾史萬歲受賄縱賊，致生邊患，毫無大臣氣節。隋文帝下令嚴查此事，查對屬實，其罪當死。隋文帝責問他：「受金放賊，重勞士馬。朕念將士暴露，寢不安席，食不甘味，卿豈社稷臣也？」史萬歲辯解說：「臣留爨翫者，恐其州有變，留以鎮撫。臣還至瀘水，詔書方到，由是不將入朝，實不受賂。」隋文帝見史萬歲心有欺隱，大怒道：「朕以卿為好人，何乃官高祿重，翻為國賊也？」並對有司說：「明日將斬之」(《隋書-史萬歲列傳》)。史萬歲懼而服罪，向隋文帝頓首請命。左僕射高熲和左衛大將軍元旻等見他已認罪，便也為他說情：「史萬歲雄略過人，每行兵用師之處，未嘗不身先士卒，尤善撫御，將士樂為致力，雖古名將未能過也」(《隋書-史萬歲列傳》)。隋文帝聽後，怒氣稍解，將他削官為民。一年後，恢復官爵，授河州(今甘肅省臨夏東北)刺史，兼領行軍總管，以防備胡人來犯。
隋開皇十九年(599年)，突厥都蘭可汗被部下所殺，其部落大亂。為挽救突厥頹勢，達頭可汗自立為步迦可汗，於開皇二十年(600年)四月率兵進犯隋邊。隋文帝命晉王楊廣、尚書右僕射楊素出靈州(治回樂，今寧夏靈武西南)，漢王楊諒與史萬歲出朔州(治善陽，今山西朔縣)，合擊步迦可汗。史萬歲率柱國張定和、大將軍李藥王、楊義臣出塞，軍至大斤山(即今內蒙大青山)，與步迦可汗軍遭遇。步迦可汗派人問：「隋將為誰？」偵察騎兵報告說：「史萬歲也。」步迦可汗又問：「得非敦煌戍卒乎？」偵察騎兵說：「是也」(《隋書-史萬歲列傳》)。步迦確定隋軍統兵將帥是當年威震敦煌的史萬歲後，慌忙引軍回撤。史萬歲揮馬追擊百餘里，大破突厥軍，斬殺數千。又繼續跟蹤追入沙漠數百里，凱旋而歸。
史萬歲自大斤山回京後，楊素妒忌其功，在隋文帝面前譖言史萬歲，說：「突厥本降，初不為寇，來於塞上畜牧耳」(《隋書-史萬歲列傳》)。遂埋沒其功，不予褒獎。史萬歲數次上表陳述，隋文帝仍未醒悟。此時隋文帝從仁壽宮初還京師，並剛廢掉太子楊勇，所以嚴防東宮結黨謀變。隋文帝問史萬歲現在何處，其時史萬歲正在朝堂，但楊素見隋文帝正怒，卻故意說：「萬歲謁東宮矣」(《隋書-史萬歲列傳》)。以激怒隋文帝。隋文帝果然信以為真，立即下令召見史萬歲。當時出征將士數百人在朝稱冤，史萬歲對眾人說：「吾今日為汝極言於上，事當決矣」(《隋書-史萬歲列傳》)。史萬歲見到隋文帝后，說：「將士有功，為朝廷所抑」(《資治通鑒-卷第一百七十九》)！言辭憤激，有忤於上。楊堅越發震怒，令武士將史萬歲暴殺於朝堂。既而後悔，但已追之不及。只好下詔加罪於史萬歲：「柱國、太平公萬歲，拔擢委任，每總戎機。往以南寧逆亂，令其出討。而昆州刺史爨玩包藏逆心，為民興患。朕備有成敕，令將入朝。萬歲乃多受金銀，違敕令住，致爨玩尋為反逆，更勞師旅，方始平定。所司檢校，罪合極刑，捨過念功，恕其性命，年月未久，即復本官。近復總戎，進討蕃裔。突厥達頭可汗領其凶眾，欲相拒抗，既見軍威，便即奔退，兵不血刃，賊徒瓦解。如此稱捷，國家盛事，朕欲成其勳庸，復加褒賞。而萬歲、定和通簿之日，乃懷奸詐，妄稱逆面交兵，不以實陳，懷反覆之方，弄國家之法。若竭誠立節，心無虛罔者，乃為良將，至如萬歲，懷詐要功，便是國賊，朝憲難虧，不可再捨」(《隋書-史萬歲列傳》)。死之日(十月初九，即公元600年11月20日)，天下人聞者，識與不識，莫不冤惜。有子史懷義。