苏武的伤势逐渐痊愈，单于又派使者劝降苏武，让他参加对虞常的审判，想借此逼苏武投降。匈奴人当着苏武等的面斩杀了虞常，卫律说：“汉使张胜谋杀单于亲近的大臣，按律当死，单于说了，投降可以免罪。”说完举剑假装要杀张胜，张胜慌忙请求投降。卫律又对苏武说：“副使有罪，正使应付连带责任。”苏武答：“我没有参与，又不是他的亲属，我为什么要负责？”卫律恼羞成怒，又举剑对着苏武，但苏武面不改色，岿然不动。
硬的不行，卫律又来软的。卫律说：“苏君，我之前背弃汉朝归顺匈奴，有幸受到了单于的恩宠，赐我为王，现在我拥有部众数万，牛羊满山。如今你若投降，也会像我一样富贵，否则陈尸于荒野，谁又能知道你呢？”苏武根本不理会他。卫律又说：“苏君，今天如果你听我的话投降，我即与你结为兄弟，否则日后想见我都不可能了。”苏武大骂道：“你身为大汉臣子，却背叛朝廷，丧失气节，有何颜面让我见你？如今单于对你委以重任，你却不能主持公正，想挑起匈奴与汉朝两国的事端。我警告你，历来杀害汉使的国家都没有好下场。南越国杀了汉使，被汉朝大军所灭，成为汉朝的九个郡；大宛王杀了汉使，他头颅被汉军砍下，挂在朝廷的北阙；朝鲜国杀了汉使，随即被灭国。现在只有匈奴还没有遭此下场，你明知我不会投降，如果以此为借口杀我，导致两国交战，匈奴的灭顶之灾就要由你引起。”
卫律知道苏武不会屈服，将情况报告单于。单于却越发想让苏武投降，就把苏武囚禁在大土窖，不给他饮食，企图折磨他的意志。正好天上下雨雪，苏武躺在土窖里，用雪拌着毡毛一起吞下，竟然连续数日不死。匈奴人以为苏武有神灵相助，便把他迁移到北海（今贝加尔湖）无人烟的地方，让苏武放牧一群公羊，说要等公羊产奶、生下羊羔，苏武才能离开。同时把常惠等人安置到别的地方。
苏武到了荒无人烟的北海，吃的、住的都没有，只好挖掘野鼠贮藏的草籽充饥。即便如此，苏武依然意志坚定，在茫茫北海手持出使匈奴的节杖放牧着羊群。天长日久，节杖上的旄饰已经脱落，但苏武仍然日日夜夜手不离杖。
牧羊五六年后，苏武的处境有了转机。当时的狐鹿姑单于的弟弟於靬王，在北海射猎，他采用的弋射是将细绳系于箭上射出。苏武担任过栘中厩监，掌管鹰犬射猎，懂得用网做成丝绳，又懂得校正弓弩，对於靬王的射猎很有帮助，因而深受对方敬爱。於靬王送给苏武足够的粮食和衣物，很可能还找匈奴女子配给苏武为妻。三年后，於靬王生病，仍赐给苏武马匹、牛羊、衣服及居住的穹庐。不久於靬王去世，他带来的随身人员也相继离去。这年冬天，居住在北海的丁令族人盗走了苏武牛羊，苏武再次陷入困厄之境。
当初苏武和李陵都在朝中任侍中，关系甚好。苏武出使匈奴第二年，李陵兵败投降，一直不敢去见苏武。许多年后，新即位的狐鹿姑单于派李玲劝降苏武。李陵到达北海，为苏武设置酒宴，转达了单于对苏武的诚意，并告诉苏武离汉后家里的许多变故：苏武做奉车都尉的哥哥苏嘉，跟随武帝到雍县棫阳宫，扶辇车下台阶时撞了柱子，车辕折断，被弹劾为大不敬罪，苏嘉伏剑自杀，朝廷赐钱二百万安葬。弟弟苏贤跟随武帝到河东祭祀后土祠庙，宦官骑兵与黄门都尉抢船，将黄门都尉推入河中淹死，肇事宦官骑兵逃跑，武帝下令苏贤去抓捕，没有抓到，苏贤惶恐之下服毒自尽。苏武的母亲已经去世，李陵还参加了苏母在阳陵的安葬。苏武的妻子还年轻，听说已经改嫁。家中只有两个妹妹和苏武的两个女儿、一个儿子，10多年过去了，也不知道他们的死活。
李陵劝苏武：“你独自留在这荒无人烟的地方，谁又能看到你的忠义呢？人生好似朝露，何必这样苦了自己。我刚投降时也痛恨自己为何要背叛朝廷，加上老母收留在保宫。你不想投降的心情能超过我当年吗？如今陛下年老，法令无常，大臣无罪被灭族的就有几十家，常有生死难料的感觉，你这样坚守又为了谁呢。希望你能听进我的苦言相劝，不要拒绝。”苏武仍义正词严地说：“我们苏家父子的一切，都是皇上赐予的，我侍奉皇上，犹如儿子侍奉父亲，我愿为皇上肝脑涂地，死而无憾！”
李陵与苏武一连喝了几天酒，李陵最后说：“你就听我一句忠言吧！”苏武说：“我早就死过一次，你一定要我投降，就趁着今天的酒宴，让我死在你面前。”李陵见苏武如此赤诚，喟然长叹：“这才是真正的义士！我李陵和卫律的罪，只有让苍天审判了。”说罢热泪盈眶，大颗的泪珠落在衣襟上，与苏武告别。