愛國主義的全盛時期,國家的士兵們正準備遠赴戰地。把花兒裝飾在槍上,在歡呼中行走著。在荒郊野外裡,竟出現了一個專吃美女心臟的巫師霍爾,以及會移動的城堡。
在荒地附近的城鎮,有一位少女蘇菲,十八歲,在城鎮上出生長大,接下了死去的父親所遺留下來的帽子店。妹妹莉蒂則是個交際花,因待人親切,是城鎮上最好的咖啡廳~茄佳里的活招牌。蘇菲被妹妹問道:「你真的想接管這家帽子店嗎?」可是,個性認真的蘇菲只有辛勤的工作。只是有時一個人的時候,會想想自己到底想做些什麼事呢?!
一天,蘇菲在街上遇到一位美男子。好像在被什麼追趕的青年,忽然抱起蘇菲一同飛上天空,在空中散歩,蘇菲的心已深深地被霍爾吸引。但是卻在那天晚上,蘇菲被一位名叫荒地魔女的女巫施了魔法,外表竟然變成了九十歲的老婆婆。蘇菲心想這個模樣不能再待在家裡,只好整理行李,遠離人群,前往荒郊野外中,霍爾所居住的城堡。
前往荒郊野外沿途,蘇菲解救了一個稻草人的卡卡西的同時,出現了一座巨大的城堡,竟用著四條腿走路移動。為了避寒的蘇菲,躲進城堡裡,出來迎接她的,卻是能讓暖爐燒更加旺盛的火惡魔可兒西法,他說著「即使是霍爾,也不會想吃這老婆婆的心臟吧!」。可兒西法跟霍爾立了合約,所以才會把暖爐綁在身上,且他們有個交易,如果可兒西法能識破合約裡的秘密的話,就能變回原本的樣子。蘇菲決定以女佣的身分,住進移動的城堡裡。
每天分別使用各式各樣的名字,過著無所事事生活的霍爾,拒絕了強大國家的徵召。與霍爾的徒弟,少年的馬克,及稻草人的卡卡西,展開了奇妙的同居生活,蘇菲很快地就習慣了。不論是美男子霍爾,或是能移動城堡的火惡魔,對一個老婆婆來說,都是相當危險的。
那時統治史柏麗王國的是莎莉蔓女巫。那時史柏麗王國並沒有加入戰爭。但戰火愈來愈接近蘇菲所居住的城鎮,霍爾將採取什麼行動呢?且蘇菲向霍爾要求什麼樣的事情呢?