戰國時代末期，遊牧民族在塞外相互結盟，逐漸形成月氏、東胡與匈奴三大勢力。漢朝初期，高祖被匈奴擊敗，約定以宗室女和親，並定期進貢給匈奴。至漢武帝時期，改變政策與匈奴進行長期戰爭。建元四年（公元前139年），張騫出使大月氏，打算與月氏人結盟夾擊匈奴，無功而回。可是張騫發現西域另有一個強大的烏孫國，能切斷匈奴右臂，建議漢武帝拉攏。

漢武帝以宗室女細君公主嫁與烏孫，軍須靡封她為右夫人，極為寵愛。可惜才過幾年，細君公主就在懷孕期間病逝。烏孫隨即派遣特使團前往長安，一方面通報細君公主的死訊，同時請求迎娶另一位和親公主。

【電視劇省去了細君公主先嫁給獵驕靡的那一段。而且從此處開始，就幾乎全是杜撰，除了幾位主角，其他人物和故事幾乎都不存於史實。】

由左將軍翁歸率領的烏孫特使團在沙漠遇匈奴突襲，團中士兵多半戰死。翁歸和匈奴人繼續纏鬥，讓副將脫身往長安報訊。細君公主之死使朝廷震驚，漢武帝決定不下是否派出另一位公主。

此時一個漢人戲班子在敦煌附近的沙漠，班裡的女孩解憂正四處找水。好不容易看見一個小湖，旁邊卻有一群人在惡鬥，直到其中一個把其他人都殺了。解憂走過去，看到湖水被汙染，氣得大罵。那個凶神惡煞不聲不響跨上馬，狠狠瞪了解憂一眼才走。這是解憂第一次見到翁歸。

戲班子長期在西域一帶表演，除了班主和他的兒子，還有幾個賣藝人，其中兩個是女孩。阿彩溫柔體貼，是戲班子的台柱；解憂聰明俏麗，點子最多，但有時脾氣不太好。他們解決了飲水問題，走到下一個小鎮，搭起台子開始表演。

身受重傷的翁歸也找到這個小鎮。為了甩開跟蹤的匈奴人，他往人多的地方鑽，擠到戲台邊。阿彩正頂著罈子走繩索，瞥見台下幾個帶刀的匈奴人，一失神掉下來，腳也扭傷了，不能再表演。班主苦惱沒有壓軸好戲，解憂自告奮勇上台表演魔術，結果遇到躲在箱子裡的翁歸。匈奴人跳上台檢查箱子，觀眾嚇得四散逃逸，翁歸也不見了。

戲班子找了一間破屋過夜，解憂打開箱子，發現翁歸又在裡面，已經昏迷了。班主檢查一下，發現他肩上的傷有毒，命在旦夕。解憂用她在湖邊撿到的小刀為這個不速之客刮骨療毒。簡陋的工具，粗淺的技術，即使翁歸這樣的鐵漢也經不起劇痛折磨。手術完成，翁歸說小刀是他的。

翁歸傷勢漸好，要求班主收留他。不巧和解憂出去找水的時候又遇到匈奴的義律，兩人施計脫逃，解憂卻把隨身玉珮掉在半途中，那是父母留給她的唯一紀念。翁歸回頭去找，為了取信，他把那隻曾被拿來刮骨拔毒的小刀交給解憂，約定找到玉珮時再來交換。

匈奴人不甘受愚弄，義律憑記憶叫人畫出翁歸的小刀，註明拿刀的人是匈奴的奸細，然後把這個假訊息傳給駐守敦煌的漢朝騎都尉李陵。

解憂隨戲班子到了敦煌，準備登台表演，被李陵的部下搜出圖畫上的小刀，當成奸細抓進營裡。翁歸得知消息，也假裝成奸細讓守軍抓起來，趁李陵準備行刑的時候救了解憂 ... 不過先哄她答應嫁給他。

李陵向翁歸和解憂道歉，同時見到了解憂的玉珮。解憂一直希望透過玉珮找到親生父母，李陵建議她去長安找淮天沙將軍。

戲班子到了長安，翁歸和解憂找到淮將軍府邸，等了許久才見到淮天沙，但一直不給解憂說話的機會。翁歸離開去找他的部將，得知武帝對和親之事沒有肯定答覆。而解憂在淮天沙府前等了幾天都沒有說上話，聽說將軍正為籌辦楚王太夫人的壽禮煩惱，於是在下一次見到淮天沙時，自告奮勇為他解決壽禮的問題。

楚王的母親曾在敦煌住過，解憂建議淮天沙讓戲班子在壽誕時表演，作為賀禮。同時藉著李陵的薦信，希望淮天沙為她解玉珮之謎。淮天沙查看了玉珮，不願多說甚麼，只要求解憂和戲班子好好表演。

解憂和戲班子有了妥善安排，翁歸決定離開去執行和親任務，但沒有透漏給任何人，只是把珍愛的小刀留給解憂，告訴她保管好。不論她在哪裡，憑著這把刀，他一定會去找她。

戲班子的表演果然讓楚王母親讚賞，尤其是解憂跳的那支舞，更讓人驚艷。

淮天沙給了重賞，解憂準備離開，卻受到賓客張將軍調戲。淮天沙上前阻止，和張翁打了起來。楚王聞訊，責問解憂。淮天沙出示解憂的玉珮，因而發現她是楚王失散多年的姪女。

解憂的父親是原來的楚王，因為參與謀逆被發配西域，和妻子病逝於斯。在他們病重時把兩歲的解憂留在戲班子外面，讓班主撿到收養。楚王從玉珮和解憂的外貌確認她是亡兄的女兒，要她拜見祖母，同時留宿楚王府。

【歷史上的劉解憂是楚王劉戊的孫女。劉戊是漢景帝的堂兄，景帝三年（公元前154年）參與七國之亂兵敗自盡。所以謀反的是解憂的祖父，不是她父親，也沒有發配西域這回事。劉戊去世時武帝還是個小孩子，解憂還沒有出生。】

翁歸多次朝見漢武帝，剖析漢烏和親之必要，終於讓武帝同意派遣另一位和親公主。當得知匈奴也將與烏孫和親，武帝答應數日內就會選出合適人選。翁歸達成任務，趕緊去找解憂，卻不知道她已經住進楚王府，戲班子也搬到別處去了。

楚王的女兒靖君公主從小嬌生慣養，刁蠻任性，自解憂住進楚王府就多方刁難。淮天沙發現靖君想用啞藥陷害解憂，決定帶她逃離長安。而此時翁歸正大街小巷打聽戲班子和解憂的下落。

淮天沙帶解憂出了長安城，恰巧遇見皇帝。漢武帝以為解憂是靖君公主，指示他們回去，並說三日之內王孫公主不許出城。

隔了一天，武帝傳旨令各王府宗室送適齡女兒至皇宮，甄選和親公主，靖君也在其中。她要求解憂作陪，解憂遂以陪同侍女的身分進了皇宮。

皇帝看到解憂，叫了一聲"靖君"，靖君應聲答應，卻變成犯了欺君之罪。解憂面對武帝的盛怒，解釋誰也沒有犯罪，是皇上自己認錯了人。漢武帝哈哈大笑，決定讓這個勇敢的女孩擔當和親任務。於是賜前任楚王的孫女劉解憂為公主，準備前往烏孫和親。

解憂根本不想當甚麼公主，更不願意去和親，一心一意只待翁歸來找她。可是翁歸始終沒有出現，她想逃離楚王府，又被淮天沙攔回來。

淮天沙的父親原是御前侍衛，受連累被賜死。武帝留下天沙，讓他繼續效命。淮天沙名為楚王府護衛，其實也是為武帝監視，包括解憂的行動。但他心裡同情解憂，決定再帶她逃離。楚王得知非但不阻止，還拿出令牌幫助他們。

漢武帝顯然得到密報。淮天沙帶著改穿男裝的解憂走到城門，拿出楚王府的令牌。士兵立即將解憂拿下，並說淮天沙密報有功，要他去見皇上領賞謝恩。

解憂被抓到皇帝面前，力辯自己不適合當和親公主。這時楚王來領罪，願意以靖君替代解憂去和親。武帝威脅要處死楚王，逼得躲在簾後的解憂出來，答應當和親公主，換取叔父一家人的性命。

解憂在後宮見到阿彩，得知皇帝早已安排好讓阿彩陪她去烏孫。心思單純的阿彩為這事高興得很，因為往後吃穿都不愁了，解憂卻擔心從此失去自由，和翁歸將形同陌路。

武帝決定對淮天沙再寬大一次，但是不能留他擔任御前侍衛。淮天沙志願陪解憂去烏孫，終身保護她安全。

經過數月準備，懷天沙和解憂帶著大批人馬出發和親，漢武帝親送至城門。臨行前，解憂請求年老時可以回長安，以歸葬故土。武帝答應將來解憂公主若是回來，他的子孫必去長安城外迎接。

翁歸回到烏孫，向軍須彌報告，同時請求再去長安。昆彌指示他先接回大漢和親公主。

和親團出了玉門關，遇到由馮嫽率領的駱駝商人。淮天沙不信任馮嫽，兩人一言不合打了起來。解憂拆穿了馮嫽實為女扮男裝，邀她同行藉此了解西域。

【歷史上馮嫽才是陪解憂嫁到烏孫的使女，不是甚麼假扮男裝的駱駝商人。不過後來真的嫁給烏孫的右將軍，繼解憂之後在西域折衝樽殂，是難得一見的女外交官。】

為了對抗大漢，匈奴一方面派出自己的和親公主，一方面派義律去阻撓漢朝的和親隊伍。淮天沙得到馮嫽的情報，預先做了準備。但匈奴來勢洶洶，幾乎抵擋不住。翁歸及時趕到擊退義律，淮天沙和翁歸這時才知道彼此的真實身分。

翁歸隨即晉見和親公主，為救駕來遲請罪。驚愕萬分的解憂未予答覆，卻攔不住興奮的阿彩。翁歸驚訝地招呼阿彩，然後見到從帳中出來的解憂，手裡拿著他留下的小刀。

解憂反悔，可是已經遲了。皇上對她說過: "可以選擇的是機會，不可以選擇的是命運"。擔任和親公主是她的命運，無從選擇。

她想一個人靜一靜，次日一早牽馬走到水邊。滿懷惆悵的翁歸也正好過去。解憂轉身回頭，看見幾個惡徒衝過來，欲置她於死地。翁歸趕來救援，寡不敵眾受了重傷，只能帶她逃跑。

翁歸傷勢略好，引領解憂遊覽烏孫草原，走訪附近牧民。這是他們在草原上最美好的時光。

解憂和翁歸準備回和親團，途中卻又遇襲，被抓至一個牧民區關起來。兩人沒有受刑，食物充足，但不得自由。翁歸判斷這是一群親匈奴的烏孫人。

淮天沙發現解憂和翁歸同時失蹤，帶人四處尋找。而此時一股匈奴人和附近漢軍交戰，逃逸至牧民區。漢朝將領在城鎮搜尋匈奴人，巧遇尋找解憂的淮天沙。

漢軍認為匈奴人偽裝成牧民，點燃箭鏃攻擊，卻射至解憂和翁歸的牢獄四周。兩人從火中逃出，驚見原先接待他們的牧民死於非命，連小孩都不放過。匈奴人對他們繼續攻擊，解憂受傷昏厥。

淮天沙發現解憂受困牧民區，趕去救援，翁歸正帶著她逃出來。淮天沙怪罪翁歸，讓馮嫽帶解憂回去，自己和翁歸打起來。翁歸不敵，被淮天沙丟進河裡。

其實這都是親匈奴的長山翕侯的設計，為了阻止大漢和親團，讓匈奴大單于的女兒胡姑先一步到達烏孫國都赤古城。

淮天沙偽稱翁歸已遭匈奴人殺害，帶著和親團繼續前行，解憂懷著悲痛認命的走上烏孫古道。馮嫽告訴她，邊境居民長期受戰亂之苦，盼望和親公主帶來和平，她不能讓他們失望。另一方面，長山翕侯不相信翁歸遇害，但利用機會挑撥昆彌對大漢和親使團的敵意，並請昆彌先迎娶匈奴公主胡姑。

解憂歷盡千辛萬苦到達赤古城，遇到懷有敵意的昆彌，並被安排參加胡姑的婚禮。