Katara and Sokka reunite with Bato, an old friend of theirs from the Southern Water Tribe. Bato suggests they find their father, which causes Aang to fear that his friends may leave him; when Aang intercepts a message from Sokka and Katara's father, he hides it because of this. Later, he comes clean about the message, upsetting his friends. Meanwhile, Zuko hires a bounty hunter named June to help him track down the Avatar. After defeating Zuko, Aang reclaims Katara's necklace and returns it to her. Katara and Sokka decide they cannot leave Aang, as he is part of their family, too.
Aang finds a whale's tooth scimitar, which Sokka quickly identifies as a Water Tribeweapon. The team begins to search for any other traces of the passage of the Water Tribe warriors through the area; Sokka finds a burned arrow and further evidence of a fight between firebenders and the warriors of the tribe. Their search eventually leads the trio to the shore where Katara sees a stranded boat, which she and Sokka recognize as part of their father's fleet.
Meanwhile on his ship, Zuko and his uncle are drinking tea and relaxing when the ship suddenly rocks, causing the tea to spill all over Zuko. On deck, he finds a bounty hunter named June mounted on a large animal called a shirshu. June states that she is looking for a stowaway, ignoring Zuko's denial of there being a stowaway on his ship. The beast tears out a hunk of metal from the deck with its strong teeth and, following the stowaway's scent, ultimately finds his prey. The fugitive tries to escape only to be stunned when the beast uses his whip-like tongue to temporarily paralyze him. As June prepares to mount her shirshu with the fugitive in tow, Zuko inquires as to how she knew of the man's hideout, to which she replies that it is due to the shirshu's sense of smell. This leaves Iroh impressed with both the animal and the owner.
Later that night, Sokka remembers the day that Hakoda, his father, left the Southern Water Tribe, leaving him to take care of his little sister. Just then, Bato, a friend of Hakoda's family and a native of the South Pole, appears at the group's campsite next to the boat. Bato explains that he was injured and left behind, and takes the party to his current home in an abbey of nuns who make perfumes and cures.
Excited over the reunion, Sokka and Katara share stories about their tribe, but they unintentionally leave Aang out, causing him to feel excluded. In the meantime, Zuko hires June and her pet shirshu, Nyla, to capture the Avatar, using the scent of Katara's necklace, and offers her weight in gold as payment. She accepts, but only when they agree raise the price to Iroh's weight in gold.
Back at the abbey, Bato states that a message is arriving soon about their father's whereabouts, so Katara and Sokka might be able to see him. Aang runs off, feeling hurt that Katara and Sokka might leave him to go find Hakoda. However, Aang does not hear the last part of the conversation when they reject the offer, saying they must travel to the North Pole with him.
While Aang is contemplating their possible departure, he receives a rendezvous map from Hakoda, delivered through a messenger who stands before him. Instead of giving it to the others, Aang hides it to ensure Katara and Sokka stay with him, and returns to Bato's home acting awkwardly. Meanwhile, Zuko, June, and Iroh search for Aang in the ruins of Taku, worrying the herbalist who thought her cat, Miyuki, had gotten into trouble with the Fire Nation again.
The next day, Aang hides the footprints of the messenger's ostrich horse when Bato takes Sokka and his friends on a coming-of-age ritual called ice dodging. Because of the lack of ice in that region, they are forced to navigate through jagged rocks instead. Meanwhile, Zuko continues his search, arriving at Aunt Wu's place in Makapu Village. Back on the ice-dodging ship, with help from the bending of Katara and Aang under Sokka's conduct, they pass the test and the members of the group each receive a ceremonial mark: the mark for wisdom for Sokka, bravery for Katara, and trust for Aang. When Aang receives this mark, he is overwhelmed with guilt and nervously reveals the rendezvous map, giving it to Katara and Sokka. Sokka, furious at Aang's secrecy, yells at him harshly while Katara expresses disappointment; they leave Aang to find their father.
Soon afterward, the shirshu arrives at the abbey, closing in on its prey. Katara, traveling with Sokka and Bato to find Hakoda, hears a wolf howling. Sokka suggests that the wolf is hurt, but Bato tells them that the wolf has simply been separated from its pack. He explains how he can relate to this, telling Sokka and Katara about that when he was left by his fellow warriors in the abbey to heal after being wounded in battle, he felt the loneliest he had ever felt. This story reminds Sokka of when Hakoda left to fight abroad. Sokka and Katara realize their mistake in leaving Aang and turn around to find and apologize to him, who meanwhile is almost ready to leave when Mother Superior warns him of Zuko's approach.
Zuko, Iroh, and June find Katara and Sokka, and learn that the Avatar is not with them. The shirshu paralyzes the siblings as they try to escape and finds the map, which has Aang's scent. Following the scent, they return to the abbey, where they find Aang waiting for them. Flying on his glider, he manages to take the beast down. June quickly rises and, once on her shirshu, tries to attack Aang, but is stopped by Appa. Aang and Zuko start fighting, eventually creating a large explosion. Nyla attempts to paralyze Appa with his tongue while nearby, Zuko recovers from the explosion and starts firebending at Aang, who is also being chased by the shirshu. Appa tries to aid his owner by firing air blasts at his chaser, albeit unsuccessfully. Zuko resumes his duel with the Avatar, the latter of whom notices Katara's necklace in Zuko's fist and, after dodging his fire whips atop a well, manages to recover it. Appa tries to reach Zuko, who is shooting fire at Aang, but June and the shirshu manage to paralyze the bison after numerous attacks.
Meanwhile, Zuko and June finally corner Aang against a wall. Sokka devises a plan and has the nuns pour out all their vats of perfumes; Katara starts waterbending the perfume into a thick mist. Since the shirshu can only "see" with its nose, the excess of different scents becomes a smokescreen of sorts, causing it to become overwhelmed and lash out haphazardly. When Zuko and June are paralyzed by the beast, Iroh pretends to have been paralyzed as well in order to get close to June, holding her in his arms as he lies on the ground. Aang and the others use the opportunity to escape.
Later, when the group is flying away on Appa, Aang asks them about their current plans. They inform him that they will travel to the North Pole because he has become part of their family, and they need each other. Aang returns Katara her necklace, saying that Zuko asked him to do so. Katara understands the joke, and kisses Aang on the cheek. With that, Aang blushes and twiddles his thumbs as they fly off into the sunset.
Katara's necklace, which she lost in the episode "Imprisoned", is recovered by Aang during his battle with Zuko and returned to her.
The herbalist and her pet cat Miyuki make a return appearance in this episode. She is seen gathering herbs near the ruins of Taku.
June, Zuko, and Iroh make a stop at Makapu Village and briefly converse with Aunt Wu. June comments that Katara must have spent a lot of time there, referring to Katara's repeated visits to have her fortune read.
The man June was arm-wrestling appears later in the series fighting her.
When Bato says the sisters craft perfume and ointments, Katara is seen wearing her mother's necklace even though, at that point, Zuko has it.
When June runs off the dock after having captured the stowaway on Zuko's ship, the stowaway cannot be seen.
In a distant shot of the abbey, the doors are open. The next moment, when Zuko, Iroh, and June enter, they break through the door that was already open.
When Katara and Sokka are by the boat, Aang's footprints disappear. In the next scene, they reappear.
When Katara and Sokka find out Aang had the map that would lead them to their father, Sokka, Katara, and Bato's footprints can be seen. When Sokka, Katara, and Bato are walking away, their footprints disappear.
Zuko and June stop at the hilltop herbalist in their pursuit of Aang, despite the fact that Katara never went there.
When Bato is saying he cannot do anything while ice dodging, Katara's rope is behind Sokka and Aang.
When Sokka is yelling at Aang, the mark on his forehead is an arch, but when he turns back at Katara, it is more triangle-shaped.
When Nyla strikes Zuko with his tongue, June is on the saddle, but in the next frame where Nyla strikes June, she is off the saddle.