史萬歲，京兆杜陵人也。父靜，周滄州刺史。萬歲少英武，善騎射，驍捷若飛。好讀兵書，兼精占候。年十五，值周、齊戰於芒山，萬歲時從父入軍，旗鼓正相望，萬歲令左右趣治裝急去。俄而周師大敗，其父由是奇之。武帝時，釋褐侍伯上士。及平齊之役，其父戰沒，萬歲以忠臣子，拜開府儀同三司，襲爵太平縣公。
尉迥之亂也，萬歲從梁士彥擊之。軍次馮翊，見群雁飛來，萬歲謂士彥曰：「請射行中第三者。」旣射之，應弦而落，三軍莫不悅服。及與迥軍相遇，每戰先登，鄴城之陣，官軍稍却，萬歲謂左右曰：「事急矣，吾當破之。」於是馳馬奮擊，殺數十人，衆亦齊力，官軍乃振。及迥平，以功拜上大將軍。
尒朱勣以謀反伏誅，萬歲頗相關涉，坐除名，配敦煌為戍卒。其戍主甚驍武，每單騎深入突厥中，掠取羊馬，輒大剋獲。突厥無衆寡，莫之敢當。其人深自矜負，數駡辱萬歲。萬歲患之，自言亦有武用。戍主試令馳射而工，戍主笑曰：「小人定可。」萬歲請弓馬，復掠突厥中，大得六畜而歸。戍主始善之，每與同行，輒入突厥數百里，名讋北夷。竇榮定之擊突厥也，萬歲詣轅門請自効。榮定數聞其名，見而大悅。因遣人謂突厥曰：「士卒何罪過，令殺之，但當各遣一壯士決勝負耳。」突厥許諾，因遣一騎挑戰。榮定遣萬歲出應之，萬歲馳斬其首而還。突厥大驚，不敢復戰，遂引軍而去。由是拜上儀同，領車騎將軍。平陳之役，又以功加上開府。
及高智慧等作亂江南，以行軍總管從楊素擊之。萬歲率衆二千，自東陽別道而進，踰嶺越海，攻陷溪洞不可勝數。前後七百餘戰，轉鬭千餘里，寂無聲問者十旬，遠近皆以萬歲為沒。萬歲以水陸阻絕，信使不通，乃置書竹筒中，浮之於水。汲者得之，以言於素。素大悅，上其事。高祖嗟歎，賜其家錢十萬，還拜左領軍將軍。
先是，南寧夷爨翫來降，拜昆州刺史，旣而復叛。遂以萬歲為行軍總管，率衆擊之。入自蜻蛉川，經弄凍，次小勃弄、大勃弄，至于南中。賊前後屯據要害，萬歲皆擊破之。行數百里，見諸葛亮紀功碑，銘其背曰：「萬歲之後，勝我者過此。」萬歲令左右倒其碑而進。渡西二河，入渠濫川，行千餘里，破其三十餘部，虜獲男女二萬餘口。諸夷大懼，遣使請降，獻明珠徑寸。於是勒石頌美隋德。萬歲遣使馳奏，請將翫入朝，詔許之。爨翫陰有二心，不欲詣闕，因賂萬歲以金寶，萬歲於是捨翫而還。蜀王時在益州，知其受賂，遣使將索之。萬歲聞而悉以所得金寶沉之於江，索無所獲。以功進位柱國。晉王廣虛衿敬之，待以交友之禮。上知為所善，令萬歲督晉府軍事。明年，爨翫復反，蜀王秀奏萬歲受賂縱賊，致生邊患，無大臣節。上令窮治其事，事皆驗，罪當死。上數之曰：「受金放賊，重勞士馬。朕念將士暴露，寢不安席，食不甘味，卿豈社稷臣也？」萬歲曰：「臣留爨翫者，恐其州有變，留以鎮撫。臣還至瀘水，詔書方到，由是不將入朝，實不受賂。」上以萬歲心有欺隱，大怒曰：「朕以卿為好人，何乃官高祿重，翻為國賊也？」顧有司曰：「明日將斬之。」萬歲懼而服罪，頓首請命。左僕射高熲、左衞大將軍元旻等進曰：「史萬歲雄略過人，每行兵用師之處，未嘗不身先士卒，尤善撫御，將士樂為致力，雖古名將未能過也。」上意少解，於是除名為民。歲餘，復官爵。尋拜河州刺史，復領行軍總管以備胡。
開皇末，突厥達頭可汗犯塞，上令晉王廣及楊素出靈武道，漢王諒與萬歲出馬邑道。萬歲率柱國張定和、大將軍李藥王、楊義臣等出塞，至大斤山，與虜相遇。達頭遣使問曰：「隋將為誰？」候騎報「史萬歲也」。突厥復問曰：「得非敦煌戍卒乎？」候騎曰：「是也。」達頭聞之，懼而引去。萬歲馳追百餘里乃及，擊大破之，斬數千級，逐北入磧數百里，虜遁逃而還。楊素害其功，因譖萬歲云：「突厥本降，初不為寇，來於塞上畜牧耳。」遂寢其功。萬歲數抗表陳狀，上未之悟。會上從仁壽宮初還京師，廢皇太子，窮東宮黨與。上問萬歲所在，萬歲實在朝堂，楊素見上方怒，因曰：「萬歲謁東宮矣。」以激怒上。上謂為信然，令召萬歲。時所將士卒在朝稱寃者數百人，萬歲謂之曰：「吾今日為汝極言於上，事當決矣。」旣見上，言將士有功，為朝廷所抑，詞氣憤厲，忤於上。上大怒，令左右㩧殺之。旣而悔，追之不及，因下詔罪萬歲曰：「柱國、太平公萬歲，拔擢委任，每總戎機。往以南寧逆亂，令其出討。而昆州刺史爨翫包藏逆心，為民興患。朕備有成勑，令將入朝。萬歲乃多受金銀，違勑令住，致爨翫尋為反逆，更勞師旅，方始平定。所司檢校，罪合極刑，捨過念功，恕其性命，年月未久，卽復本官。近復總戎，進討蕃裔。突厥達頭可汗領其兇衆，欲相拒抗，旣見軍威，便卽奔退，兵不血刃，賊徒瓦解。如此稱捷，國家盛事，朕欲成其勳庸，復加褒賞。而萬歲、定和通簿之日，乃懷姦詐，妄稱逆面交兵，不以實陳，懷反覆之方，弄國家之法。若竭誠立節，心無虛罔者，乃為良將，至如萬歲，懷詐要功，便是國賊，朝憲難虧，不可再捨。」死之日，天下士庶聞者，識與不識，莫不寃惜。
萬歲為將，不治營伍，令士卒各隨所安，無警夜之備，虜亦不敢犯。臨陣對敵，應變無方，號為良將。有子懷義。