【星塵傳奇】一片的故事從一個叫「牆」的小小英國村莊開始，這個小村莊以自古以來就環繞著整個村莊的一道牆為村名，因為這道神奇的石牆保護著村民，不被石牆另一邊的超自然宇宙侵略。但是有一天有一個情竇初開的小伙子崔斯坦索恩（查理考克斯飾演）為了贏得美人心，向村上最美的姑娘（席安娜米勒飾演）做了一個承諾，那就是把那顆墜落到地面的星星拿給她。於是崔斯坦就必須穿過禁忌的石牆，進入一個神秘的王國，成為一個偉大傳奇的一部份。

這個充滿神奇人事物的王國被稱為風暴禁域，崔斯坦在這裡發現那顆墜落的星星並非他想像的是一顆殞石，而是一個強悍有個性的女孩（克萊兒丹妮絲飾演），只是她很不幸地從天空掉落到地面時受了點小傷，而現在她又陷入更大的危險，各方人馬，包括國王（彼德奧圖飾演）的兒子，各自都想得到神秘女孩的心，成為風暴禁域的國王；另外還有一名擁有邪惡魔力的巫婆（蜜雪兒菲佛飾演）也想利用這名女孩得到永恆的青春和美貌。當崔斯坦決定保護這個女孩，並將她帶到石牆的另一邊，他就展開了一場驚險刺激的冒險之旅，他在旅途中遇到一名飛行海盜船船長（勞勃狄尼洛飾演）以及一個老奸巨猾的商人（瑞奇吉瓦斯飾演）。但是如果他能利用他的機智和尋找到真愛的勇氣，他就能發現自己的身世之謎，也能實現他想像不到的偉大宿命。