萧兀纳，又名挞不也，字特免，六院部人。其先祖曾任西南面拽剌。
兀纳身材魁梧，庄严持重，擅长骑射。清宁初，其兄图独因事入京朝见，道宗问族人中谁人可以任用，图独回答说是兀纳，皇上补兀纳为祗候郎君。迁任近侍敞史、护卫太保。
大康初，任北院宣徽使。当时乙辛已经陷害了太子，于是称宋魏国王和鲁斡之子耶律淳可以立为太子，群臣无人敢言，只有兀纳及夷离毕萧陶隗劝谏说：“放弃嫡孙不立，这是把国家给予别人。”皇上犹豫不决。五年(1079)，皇上出猎，乙辛请求留下皇孙，皇上想听从。兀纳奏道“：我私下听说皇上出游，准备留下皇孙，倘若保护者不称职，恐怕会生变故。果真要留下，我请求侍从皇孙左右。”皇上领悟，命令皇孙从行。从此，皇上开始怀疑乙辛。
不久，任同知南院枢密使事，出贬乙辛、耶律淳等人。皇上嘉许他的忠心，封为兰陵郡王，人们说他很像古时扶持社稷的重臣。授殿前都点检。皇上对王师儒、耶律固等人说：“兀纳忠诚纯正，即使是狄仁杰辅佐唐室，屋质扶立穆宗，都没法超过他。我的看法你们要转达给燕王知道。”从这以后，皇上令兀纳辅导燕王，更加受到优待宠信。大安初，诏令让他娶越国公主，兀纳坚决推辞。改任南院枢密使，上奏请求对于掾史应按月升迁叙用，皇上从之。寿隆元年(1095)，拜为北府宰相。
当初，天祚尚未即位时，兀纳多次因为直言拂逆了其心意。待到即位，出贬兀纳为辽兴军节度使，守太傅。因佛殿小底王华诬陷兀纳借用内府犀角，诏令审讯他。兀纳上奏说：“我在先朝时，诏令准予每天取用十万钱作为私下费用，我不曾胡乱取用一钱，难道会借用犀角吗？”天祚更加恼怒，褫夺其太傅官职，降为宁边州刺史，不久，改任临海军节度使。
兀纳上书说：“自从萧海里逃到女真，女真便有轻视朝廷之心，应该增加兵力以防不测。”皇上没有作答。天庆元年(1111)，任黄龙府知府，改东北路统军使，又上书说：“我的治所与女真接壤，观察其行为，志向不小。应当在他们发动之前，派兵攻打它。”奏章几度呈上，皇上不听。及至金兵前来进犯，交战于宁江州，兀纳的孙子移敌蹇战死，兀纳退逃入城。留下属吏防守，自己率三百骑渡混同江西行，府城便陷落了。后来与萧敌里在长泺拒战金兵，因兵败免官。五年(1115)，天祚亲征，兀纳殿后，又失败了。数日之后便与百官入宫朝见，授为上京留守。六年(1116)，耶律章奴叛乱，前来进攻京城，兀纳发放府库钱物赏赐士卒，晓谕他们以顺逆之理，修缮城池，拼死拒战。章奴一无所获便离开了。因功授副元帅，不久任契丹都宫使。
天祚因兀纳为前朝重臣，有定策扶立之大功，每每请他来询问政事，兀纳总是恳切率直作答。皇上尽管待他十分宽容，终究没能重用于他。因病去世，年七十岁。