史万岁长于骑射，602年12月，贺若弼在评价史万岁之时誉之为“骑将”。他15岁随父从军，其父在北周武帝时战死，他袭爵为太平县公；北周末年因功被授予上大将军。隋朝初年，因受到谋反的大将军尔朱绩的牵连，他被发配到敦煌成为一名戍卒；但就是这个“敦煌戍卒”却让当时雄霸北方的突厥闻之胆寒。
583年5月，隋朝秦州总管窦荣定率领九名总管步骑三万兵出凉州，和突厥阿波可汗在高越原大战，尽管阿波屡次战败，但其实力依然不可小觑。此时为敦煌戍卒的史万岁便到窦荣定的军门，请求为国效力，窦荣定早就听说史万岁的大名，一见面非常高兴；同时也想尽早结束战事，便心生一计。于是窦荣定与突厥约定“当各遣一壮士决胜负耳！”突厥当即答应。第二天，大军摆开阵势，突厥人派出一名骁勇善战的骑将如旋风般地冲出阵营，只听得鼓声阵阵，军士呐喊声直冲云霄！窦荣定见状淡然一笑，向史万岁略一点头，史万岁便拍马而出。就在两军对两名勇士要大战几百回合的精彩对决的期盼中，隋军的鼓声也是刚刚震天响起，史万岁就“斩其首而还”。出去一阵风，提着突厥勇士的首级又一阵风般地驰回，所有的突厥人都惊呆了，他们心目中最勇猛的勇士就这样一个回合都没有便陨命当场。于是，阿波等再也不敢与隋军对阵了，只能结盟撤军；更重要的是在所有的突厥人心中永远地留下了一个很难磨灭的“敦煌戍卒”的印象。
589年年初隋灭陈，但次年11月“陈之故境，大抵皆反”，隋文帝杨坚派遣杨素为行军总管去江南平叛。杨素非常信任史万岁，让他率领两千人，从婺州别道进军。一开始还捷报频传，但逐渐地失去了与史万岁的联系；当失联长达一百天的时候，杨素等人都以为史万岁肯定已经战死沙场了。突然有一天，从河中取水做饭的士兵打捞上一个封存严密的竹筒，杨素打开竹筒，才得知史万岁并未战死，而且是“前后七百余战，转斗千余里”。杨素将此事上奏隋文帝，杨坚感慨叹赏再三，觉得史万岁勇猛难得，便赏赐给史家十万钱。失联一百天，转战一千多里，取得一个又一个胜利，这就是史万岁！
597年，南宁羌叛乱，隋文帝就直接任命史万岁为行军总管，率领大军讨伐叛军。史万岁从蜻蛉川进军，直达南中。隋军集结完毕，史万岁立刻攻占叛军盘踞的一个又一个要塞，史载“皆击破之”；而且乘势深入，行军一千多里“破其三十余部，虏获男女二万余口”。那些叛军非常惧怕，便派遣使者请降，于是史万岁刻石记功，在碑文中颂扬大隋的功德。但史万岁也接受了怀有异志的爨翫的贿赂，而没有把他押送回朝。结果第二年年底，南宁羌又反叛，蜀王杨秀便上奏杨坚，说“史万岁受赂纵贼，致生边患”，史万岁一开始还狡辩不服，后来在事实面前才低头认错，隋文帝大怒“命斩之”，在高颎与元旻等人的劝解下，杨坚才没有杀史万岁，但死罪可免，活罪难除，又将他“除名为民”。当然，后来没多久又官复原职。
600年4月，突厥达头可汗率军犯塞，杨坚下诏让晋王杨广等多军出塞迎战。史万岁从马邑道出塞，军至大斤山，与达头可汗相遇。达头可汗派遣使者问：“隋将为谁？”侦测信息的骑兵回报：“史万岁也。”达头心头一震，又问：“得非敦煌戍卒乎？”当听到就是那个敦煌戍卒史万岁的时候，达头可汗冒出一身冷汗赶紧退兵。史万岁“驰追百余里，纵击，大破之，斩数千级”，并且又乘胜追击，深入大漠几百里，直到突厥军队“远遁”才凯旋。这一战，两军都未能摆开阵势，一句“史万岁也”便将突厥大军打败！但是回来后，等待他的不再是封赏，而是出自那位诗歌史上很有名的杨素嫉恨的谣言。可惜，当时的史万岁还在想着如何向隋文帝为手下的将士论功争赏，便被将史万岁认为是废太子杨勇的同党的隋文帝直接让人斩杀。尽管隋文帝也立即回味过来，但赦死之诏未到史万岁已死，然后隋文帝还是下诏“陈其罪状”。于是，天下“共冤惜之！”唐太宗李世民就曾经感慨“隋将史万岁破达头可汗，有功不赏，以罪致戮”。
《隋书》本传记述史万岁有“李广之风”。史万岁也确实与李广有很多相似之处，有“李广射虎”如此神勇的美名，就有史万岁射雁的盛誉（史万岁31岁时跟随梁士彦征讨尉迟迥的行军途中，他在众军之前说要射雁群中的第三只，结果箭发雁落）。史万岁“令士卒各随所安，无警夜之备，敌人亦不敢犯”的带兵之术及效果与李广极其相似，高颎就曾经一再感叹：“史万岁雄略过人，每行兵用师之处，未尝不身先士卒，尤善抚御，将士乐为致力，虽古名将未能过也。”此点亦与李广相同，与士卒同甘苦，冲锋陷阵在前，食饮在士卒之后，因此能得士卒死力而战无不胜了。
