史萬歲是京兆杜陵人。
他的父親史靜，是北周滄州刺史。
萬歲年輕時英俊威武，擅長騎馬射箭，勇猛凶悍，敏捷如飛。
喜讀兵書，並精通占卜。
十五歲那年，正值北周、北齊在芒山作戰，萬歲當時從父隨軍，兩軍正旗鼓相望，萬歲命令身邊的士兵迅速脫下戰衣化裝走脫，不一會兒，周軍大敗，他的父親因此對他的才能十分驚奇。
武帝年間(561～578)，他由平民百姓提升為侍伯上士。
在平定北齊的戰役中，他的父親戰死沙場，萬歲因是忠臣的兒子，晉陞為開府儀同三司，繼承太平縣公的爵位。
尉遲迥叛亂，萬歲跟隨梁士彥去平叛。
軍隊駐紮在馮翊。
一天，看見大雁飛來，萬歲對士彥說：「請允許我射下那一行中的第三隻雁。」隨即拉弓搭箭，第三隻雁應聲而落，全軍沒有不心悅誠服的。
等到與尉遲迥軍相遇時，每次他都是身先士卒。
在鄴城作戰中，官軍漸漸敗退，萬歲對身邊的士兵說：「事情緊急了，我們應當攻破敵陣。」於是躍馬上前，拚命廝殺，一口氣斬殺了幾十個敵人，大家也齊心合力，官軍的士氣於是振作起來。
剿滅尉遲迥後，萬歲因有功提升為上大將軍。
爾朱責力因謀反被處死，萬歲與這件事很有牽連，因此被罷官削職，流放到敦煌當戍邊的兵卒。
那守邊頭目彪悍威武，常常單獨一人騎馬深入突厥部落中，掠奪羊馬，總是有大收穫。
突厥無論多少人，沒有敢抵擋他的。
那頭目驕橫自負，多次辱罵萬歲。
萬歲對此很憂慮，自稱也有英武之才。
守邊頭目試探性地命令他飛馬射箭，果然射技精湛，頭目笑著說：「你定然不錯。」萬歲請求騎馬帶弓，再入突厥中掠奪羊馬，很快搶獲大批牲畜回營了。
小頭目開始對他友好，經常一起同行，常入突厥地域幾百里，聲威傳遍北夷。
竇榮定奉命攻擊突厥，萬歲到軍中請求為他效力。
榮定多次聽到他的名聲，相見後很高興。
於是派人對突厥說：「士兵有什麼罪過，何必讓他們互相殘殺呢？只在兩軍中各選一位勇士決鬥比個勝負吧！」突厥頭領答應了，因此派了一名驃騎挑戰。
榮定派萬歲應戰，萬歲衝過去，砍下突厥勇士的頭顱得勝而回。
突厥十分驚恐不敢再戰，於是率領全軍撤退了。
因這次功勞，萬歲又晉陞為上儀同，兼任車騎將軍。
平定陳國戰役中，萬歲又因戰功升為上開府。
高智慧等在江南叛亂，史萬歲以行軍總管身份跟隨楊素剿滅叛軍。
萬歲率領二千士兵，從東陽與大軍分路前進，爬山涉水，攻陷溪洞不計其數。
前後七百多次戰鬥，轉戰一千多里，與大軍失去聯繫有一百來天，遠近的人都以為萬歲戰死了。
萬歲見水陸交通阻隔，音信不通，於是將書信放在竹筒中，浮在水上，漂到了下游，打水的人得到了竹筒，將情況報告給了楊素。
楊素十分高興，向皇上陳奏了此事。
高祖得知後十分稱讚，賞賜萬歲家十萬錢，萬歲回朝後，提升他做了左領軍將軍。
從前，南寧夷人爨玩來投降，讓他做了昆州刺史，不久他又背叛朝廷。
於是委派萬歲任行軍總管率兵討伐。
從蜻蛉川進軍，經過弄凍，穿過小勃弄，大勃弄，到達南中。
叛軍前後駐紮要道，萬歲一一攻破了。
深入幾百里後，看見諸葛亮記功碑，碑文背面寫著：「萬歲以後，超過我的就過此界。」萬歲命令左右推倒石碑繼續前進。
渡過西二河，進入渠濫川，行軍一千多里，擊破三十多部落，俘虜男女二萬多人。
夷人十分震驚，派人請求投降，獻上的明珠大到一寸。
萬歲於是刻石碑稱頌隋朝功德，並派使者飛報皇上，要求押帶爨玩回朝，皇上下詔同意。
爨玩暗懷二心，不願入朝，因此用金銀財寶賄賂萬歲，萬歲受賄於是放走了他，自己就帶兵返回了。
蜀王當時在益州，知道他接受了賂賄，派使者想索取財寶，萬歲得知後將全部金銀珠寶沉到江底，蜀王一無所獲。
萬歲因平爨玩立功提升為柱國。
晉王楊廣虛懷敬重他，並用朋友的禮節待他。
皇上知道他被晉王看好，就派萬歲監管晉王府的軍中事務。
第二年，爨玩又反叛朝廷，蜀王乘機上告萬歲，說他昔日受賄放賊，致使邊防又生戰火，並說萬歲毫無大臣節操。
皇上命令追究這件事，事情都被驗證，按罪應判死刑。
皇上大發脾氣說：「我原以為你是個良臣，怎麼如今官職大俸祿重，反而變成國賊了呢？」回頭對有司說：「明天就殺掉他。」萬歲害怕處死而認罪，叩頭請求饒命。
左僕射高赹、左衛大將軍元..等替萬歲求情：「史萬歲才略非同一般，每次率軍作戰，身先士卒，又善於撫恤將士，大家樂意為他效力，即使是古代名將也難超過他。」皇上怒氣稍消，免了萬歲的死罪，將他罷官為民。
一年後又恢復了官職。
不久任河州刺史，又任行軍總管去防守胡人入侵。
開皇末年，突厥的達頭可汗侵犯邊境，皇上令晉王和楊素從靈武出發，漢王楊諒和萬歲從馬邑進軍。
萬歲率領柱國張定和、大將軍李藥王、楊義臣越過邊界，到達大斤山，與胡兵相遇。
達頭可汗派使者偵問：「隋軍主帥是誰？」使者回報道：「是史萬歲。」突厥人又問：「莫不是敦煌守卒史萬歲？」使者答：「是他。」達頭聽說是萬歲帶兵，害怕得率軍撤離了戰場。
萬歲率兵追趕一百多里才趕上了他們，擊敗了突厥，斬殺了幾千人，驅逐敵軍到沙漠裡幾百里，敵人四處逃竄。
楊素害怕萬歲功大對自己不利，於是讒害萬歲說：「突厥已經投降了，況且他們本來不是侵略，只是放牧而已。」因此隱瞞了他的功勞。
萬歲幾次上書陳述情況，但皇上還是沒瞭解到真實情況。
這時，皇上從仁壽宮剛回京都，廢掉了皇太子，窮究東宮黨羽。
皇上問萬歲在什麼地方，萬歲實際在朝中，楊素見皇上正怒氣沖沖，於是趁機說：「萬歲拜訪東宮去了。」用以激怒皇上。
皇上相信了楊素的話，命令召來萬歲。
當時萬歲所帶領的將士在朝喊冤枉的有幾百人，萬歲對他們說：「我今天把你們的功勞極力地陳述給皇上，事情會解決好的。」就去拜見皇上，陳述將士有功，卻被朝廷壓抑，他的語氣激昂憤慨，對皇上也不順從。
皇上激怒了，命令左右當場摔死了他。
萬歲死後皇上後悔不及，但為了尊嚴，還是下詔列出許多罪名。
死的那一天全國上下得知消息的，認識或不認識萬歲的，沒有一個不惋惜的。
萬歲為將領，不嚴治軍隊，讓士兵自由隨便，夜晚也沒有人警備，敵人卻不敢偷襲。
面對敵軍，隨機應變，沒有一定的方略，稱為良將。