公元前101年，且鞮侯单于初立，担心汉朝趁他地位未稳，举兵来攻，因此匈奴暂时收敛野心，派遣使者携带宝物觐见汉武帝，在国书中称汉武帝为丈人，同时释放了几百名俘获的汉朝官员。
对于且鞮侯单于的称臣纳贡行为，汉武帝很满意，决定派出使团前往匈奴王庭修好，同时探查新单于的态度。栘中厩监苏武被任命为中郎将，持节出使，副中郎将张胜、假吏常惠与一百多武士一同前往。
对于苏武来说，这是个难得的翻身机会。他的父亲苏建曾跟随卫青出征，屡立战功，爵至平陵侯，苏武兄弟几人都是蒙父荫入仕。
后来苏建在作战中私率三千人出击，全军覆没，一家人的仕途全部断送。此次出使重任完成，不仅自己，整个家族都能再次翻身。
经过几个月的长途跋涉，使团来到了匈奴王庭。且鞮侯单于妥善安置了苏武等人，接受了汉朝赠予的财物。
但见到使者，且鞮侯单于反而开始骄横起来，认为汉朝已是强弩之末，不得不接受和解，不久之后便丢下使团，自顾外出打猎去了。
苏武见单于无礼，知道他日后还会挑起战端，于是开始准备返回长安，向汉武帝如实禀告。
虞常是投降匈奴的汉人，与副使张胜有旧交。
在闲谈中，虞常告诉张胜，自己是被迫投降，在匈奴处处不得志，正在暗中联络缑王等人，准备趁单于外出，将单于母亲和阏氏绑架作为人质，回归汉朝。
张胜对虞常表示支持。还没等苏武等人动身回国，缑王、虞常等几十人便准备行动了。行动之前，其中一人突然反悔，并向匈奴贵族告发了他们。单于的亲信们火速镇压反叛，缑王当场战死，虞常被生擒。
听到这个消息，张胜将自己与虞常的谈话内容告知了苏武。苏武知道虞常经受不住拷打，肯定把张胜支持自己叛乱一事和盘托出。与其事情败露自己受辱，倒不如自行了断还能守节保住家人。
于是苏武拔出佩剑便要自刎，后被张胜、常惠等人拦下。而单于派曾生活在汉朝的丁灵王卫律审问虞常，果然不久虞常就供出了张胜。
左伊秩訾等人建议招降使团，且鞮侯单于觉得有理，于是便让卫律配合演了一出戏。卫律把苏武等人押来审问，当场宣判了虞常的死罪，并警告他们，如果不投降，全都难逃一死。
话音刚落，张胜害怕被处死，立即表示愿意归降。计谋初见成效，单于和卫律都把目光看向了苏武，自信满满地等他发话臣服。
然而苏武大义凛然地说:“若丧失气节完不成使命，还不如现在就死！”说罢又拿起剑刺穿胸口。
卫律敬重苏武为人，连忙扶住苏武叫来医生。经过几天的医治，苏武奇迹般地苏醒了。
卫律劝导苏武:“曾经我也为汉庭卖命，现在归顺匈奴，单于赐我王位，给我金山银山。
苏先生要是归降，肯定不次于我，何必冥顽不灵，死在这里给草地当肥料呢？”苏武破口大骂:“你原是大汉臣子，又给异族当牛做马，我都不愿理睬你。
现在匈奴单于信任你，你又拿别人的性命挑唆匈奴。南越王、宛王、朝鲜王这些杀了大汉使者的君主，哪个不是遭到诛杀，我要是死在这里你就是害死了单于。”
单于大受震撼，更加想将苏武纳入麾下，三番五次劝说苏武投降，许以高官厚禄，均被苏武严辞拒绝。
一气之下，单于将常惠等人分别安置，把苏武流放到北海（贝加尔湖畔），给了他一群公羊让他放牧，并放下狠话:“想回中原，除非公羊产奶！”
从此苏武每天手持节杖牧羊，时间久了节杖上的装饰物都掉光了，只剩下一根光秃秃的木棍，渴了就啃地上的雪解渴，饿了就挖草根抓老鼠充饥。
於靬王与苏武交流后欣赏他的学识，一度赠与他牲口、粮食、帐篷等。可三年后，於靬王病死，苏武失去了资助。没过多久丁零人又偷走了他的大批牛羊，苏武的生活再度雪上加霜！
李陵曾经两度到北海找苏武。第一次李陵告诉他，他的母亲已经去世，兄长担任奉车都尉，因不慎折断车辕被下狱斩杀，弟弟随皇帝祭祀，因没有追到一个犯事的宦官畏罪自杀，妻子带着子女改嫁，只剩下两个妹妹生死未卜。他在汉地已经没有亲人了，还是归降为好。
苏武出使前就与李陵交好，也知道李陵当初是兵败被生擒，单于又谎称汉皇诛灭了他全族，他迫于无奈才投降匈奴。于是苏武没有像对待卫律那样怒而谩骂，他告诉李陵，不要再提劝降的事了，否则他只能一死了之，自己忠于大汉，宁愿赴汤蹈火。
李陵陪苏武痛饮几天，临走前感慨自己投降的罪无可饶恕，又让妻子替自己送了苏武几十头牛羊。
多年后，李陵再来探望，苏武当时已经娶了一位匈奴女子为妻，也生下了孩子。
李陵告诉苏武，边境的官员百姓都身着丧服，皇帝驾崩了。
苏武痛哭流涕，向南跪拜，接连几个月每日哭吊。李陵所言不虚，这时汉昭帝即位，苏武被困在北海已经十几年了。
且鞮侯单于和他的儿子狐鹿姑单于也先后逝世，继任者壶衍鞮单于年少，其母与卫律掌权。
汉昭帝即位后改变了对匈奴的策略，采用和亲等方式改善了汉匈关系。一段时间以来，汉朝派往匈奴的使者增多，他们也曾寻找苏武的下落，但匈奴人只跟他们说苏武早就病死了。
终于一次得知使者到来后，常惠买通看守他的匈奴人，见到了使者，将自己和苏武十几年的经历原原本本地告诉使者。
随后常惠教使者，在酒宴上跟单于说:皇帝打猎时射到一只大雁，雁腿上绑着字条:武等在某泽中。
使者照做了，匈奴人不得不承认苏武还活着，并承诺放苏武回中原。历经十九年，苏武终于返回长安。