The movie starts with Sophie Hatter, a timid girl of 18, decorating hats in the hat shop of her late father. Some of the other girls exclaim as they see Howl's Moving Castle near the city. Sophie leaves the shop, and is walking home when two soldiers harass her. It is then that she has a lucky encounter with the notorious Wizard Howl. He escorts her to the bakery of her sister, Lettie Hatter. They talk, and bid farewells. Sophie returns to the hat shop, also her home, when the Witch of the Waste arrives into the shop. Jealous of her relationship with Howl, she turns Sophie into a 90 year-old grandma, and Sophie cannot tell anyone about the curse.
The next morning, Sophie decides to leave the city to find a way to lift the curse. As she enters the countryside outside of the bustling town, she meets a magical scarecrow, whom she names Turnip- Head on account of his turnip- shaped head. Turnip- Head provides Sophie with a walking stick, and Sophie, wanting to get rid of the scarecrow, asks him to find her a house as well. She chuckles at her cunning, when the scarecrow returns, bringing Howl's Moving Castle with it. Sophie, deciding there is no other option, enters. Inside, she meets the fire demon, Calcifer, flickering in the hearth. He can see through the curse, and says he will break it if Sophie can break the contract between him and Howl. At first Sophie thinks it is a trick, but decides it isn't and dozes asleep.
The next morning, Sophie is still asleep while Markl, Howl's little apprentice comes down to answer the knock on the door. He receives a letter from the mayor of Porthaven and a soldier from Kingsbury, both summoning Howl (as Jenkins and Pendragon) to the king. Sophie wakes up and proceeds to cook breakfast for them. Much to Markl's surprise, Calcifer allows Sophie to cook by using his heat. Howl returns and questions who Sophie is. Sophie says she is his cleaning lady and Howl proceeds to finish cooking. As they dine, Howl asks Sophie that what is in her pocket. She gives him a letter from the Witch of the Waste, which was in her pocket all along. Howl removes the spell from the witch and leaves, but not before asking Calcifer to move the castle and prepare a hot bath for him.
Markl questions if Sophie works for the witch, causing her to get angry, thus giving her strength to clean the dirty castle. Sophie nearly kills Calcifer as he runs out of firewood. Howl saves Calcifer and tells Sophie not to get carried away. He then leaves. Sophie proceed to the second floor and after cleaning the bathroom, she enjoyed a breath-taking view outside with Markl. They also rescue Turnip who followed her. The castle stops by a lake and Sophie, Markl, and Turnip dry the laundry. After finishing, they return to the castle and that night, Howl returns. He informs Calcifier of the fighting and the fire demon warns Howl that he wouldn't be able to turn back to human form if he continued fighting.
The next morning, Sophie and Markl goes out shopping in Porthaven. They witness a heavily damaged battleship returning from the fight and also saw the Witch of the Waste's henchmen. An enemy airship drops a few bombs then release several propaganda flyers. The two return home only to find Howl wailing and pounding down the stairs. Howl's hair has turned an orange color since Sophie mixed up his bath potions when she cleaned yesterday. Howl later throws a tantrum claiming that he isn't beautiful. He summons the spirits of darkness and generates a green see-through liquid in a humorous manner.
Sophie gets mad and briefly runs away, being jealous because as an old woman, she was never beautiful. Turnip arrive and shields Sophie from the rain with an umbrella. She later returns and together with Markl, help Howl get to the bathroom. After a while, Howl is lying in bed while Sophie gives him some hot milk. Howl reveals that he is a coward and the castle is just sorcery to keep the Witch of the Waste away. Howl says that he once took interest in the witch but became scared after he knew she used magic to keep her beautiful. That's why the witch pursued him.
The king also asked him to report to the palace as Jenkins and Pendragon. Sophie asks that why Howl can't refuse outright, which is be because the oath he made at Sorcery Academy. Howl creates a plan to send Sophie as his mother and tell the king that he couldn't come. Before going, Howl places a magic ring on her and tells her that he'll follow in disguise. Sophie walks to the palace and is followed by a dog who she believes is Howl in disguise. She meets the Witch of the Waste who is going to see the king, too. The witch takes the lead but is halted when her henchmen disintegrated due to spells casted around the palace. She leaves her palanquin and proceeds to climb the stairs.
Despite Sophie carrying the dog, she easily went ahead and the witch was terribly far behind, having great difficulty to climb the stairs. After they entered a room the witch sits down on a chair and rests. The dog runs away to another room and Sophie follows him. She is led to a garden by an aide, where she meets Suliman, the Royal Sorceress. Suliman discusses with Sophie that Howl is a student with marvelous gifts and its a shame that he won't join them. She continued Howl is a dangerous person who wields great power but has no heart. She states that if Howl won't join them she'll strip him off his powers like the Witch of the Waste.
She also informs Sophie of the Witch's history and reveals that the witch has already returned to her current age. Sophie figures some things out then tells Suliman of her peculiar tactics and explains that Howl just wants to be free. The love in her words weaken Sophie's aging curse, and Suliman realizes Sophie's relationships with Howl. Howl later arrives, disguised as the king. However, the real king appears shortly. Suliman sees through Howl's trick and tries to capture him.