The movie opens with information about World War II and its effect on Australia. It then transitions to the issue of Stolen Generations - the attempt of whites to take away aboriginal children and place them in missions to phase out the culture.
Then the movie begins, with King George, an aboriginal medicine man/witch doctor showing Nullah how to do various things in the outback. KG shows him how to fish, and Nullah successfully catches one with a spear. However, behind them is a commotion and they see cattle being driven across the river. KG tells Nullah to become invisible (he hides underwater) and a man falls dead into the water, with blood swirling around him, and an arrowhead coming out of his chest. It seems KG might have done this because, Nullah tells the audience that KG does not like white men, and he was killed by an arrow.
Nullah surfaces and a horse rears in the water. He sings to the horse and it comes over, calmly. He rides it back to where he lives, Faraway Downs. He jumps down off the horse after he sees a car coming down the road. He runs and hides in the water tower, afraid someone is going to come take him away (Stolen Generation).
But its not people to take him away, but rather Drover (Hugh Jackman), Sarah (Nicole Kidman), Magarri, and another aborigine.
Nullah, who has narrated some of the story, informs us that this story starts a while ago in another faraway place called England... Lady Sarah Ashley is off riding horses when a car pulls up with a man trying to convince Sarah not to sell Faraway Downs. She, while walking through a stable of horses, insists they could use the money. She goes to ride on another horse, finally telling the man that she will go down to Australia and sell it herself.
The film then follows Sarah on a plane, receiving various messages from her husband that she need not come down to Australia. However, she is told that she will be meeting up with her husbands helper, Drover. The city she lands in is Darwin.
About this time, the film shows Drover in a bar trying to get a drink while a man teases him about who he hangs out with (he has no problem with race). He tells his main man, Magarri, to wave his hat when the woman shows up. He then proceeds to get in a fight with most of the bar. Sarah lands, and walks down the wharf (blowing off a group of ladies sent to welcome her) with men carrying many, many cases of luggage behind her. She walks into the bar looking for Drover, her suitcases on the steps, while the fight makes its way around the bar (on the outside). They tell her women are not allowed in that bar (hence why it is empty, she responds) and she walks out to find that one of her suitcases is about to be used to bludgeon someone. As it is swung around, it flies open, spreading her undergarments around the group of men. Sarah is mortified, and is finally introduced to Drover.
Next, a very loaded up truck is driving through the outback, with Sarah wearing glasses, a hat with a net around it, gloves, and everything else that makes her overdressed for the heat and outback. Magarri is up on top on a chair. Suddenly a man starts running along side the truck, and says hello to Drover before climbing up to the top with M. Sarah notices a pack of kangaroos running next to the truck and is marveling how beautiful they areuntil the aborigine shoots one. Sarah is shocked as she watches blood drip from the top of the windshield, after the kangaroo is loaded onto the truck.
That night, she pokes her head out of her tent, only to see Drover topless. She wonders how all four of them will be in one tent, and he explains that they do not really sleep in tents, and they are not used to guests on their trips.
The next day they come to a fork in the road where an old truck is being pulled by horses. They stop and the woman driver pushes off a white man onto the road who is drunk and asleep. Sarah looks on in disgust and wants to know whom the man is; Drover informs her he is the accountant for Faraway Downs. Flynn is loaded into the truck, and Sarah can barely stand the smell of him.
An aboriginal girl runs up along Drovers side of the truck and she wants him to come hang out, but he tells her he is delivering a package. Sarah is sure that Drover is exploiting women down in Australia (she assumes her husband is doing the same) and they get into an argument. Drover is really talking about horses, but Sarah assumes he is simply referring to women as horses (mating an English thoroughbred with an Australian brumby).
Finally, they reach Faraway Downs (the house) and there is smoke and dust all around. (We get a replay of back to the beginning of the movie with Nullah) Drover tells Sarah to stay in the truck, and Magarri throws him a gun. He slowly walks the grounds, and there is a dead steer, and burning piles. Sarah angrily gets out of the truck and walks into the house, although Drover tells her not to go in. She does anyway, and sees her husband lying dead on the table.
Now it seems that Sarah really will sell the property to the Carney empire. (Faraway Downs is a decent size patch in the middle of the Carney-owned lands. If it is sold, the company will have a monopoly over the cattle business.)
That night, Sarah can barely sleep. She gets out of bed when she hears a noise. She walks outside, trying to find where it is coming from (its Nullah under the stairs). But she gets scared, so she runs back inside, but Nullah is in there, scaring her even more. He says he sung her to him, and that King George told him that shes like rain (much needed in a dry desert). He also tells her that Carney is stealing her cattle, driving them across the river (like in the beginning of the movie). All of a sudden his mother comes running in, begging her to keep her son away from the police. They hear a noise walking around outside, and they all hide behind her trunks. It is Fletcher, her husbands main driver, and he creepily opens the blinds, before closing them and walking away.
In the morning, Sarah is getting ready to leave when Fletcher comes up to her. Sarah asks about the cattle, saying that Nullah told her about them. He turns around, not so happy, asking Nullah to come to him (the night before, we see Fletcher come out of place where Nullah and his mother live. So Nullah is Fletchers son.) His mother and grandmother tell him in their native language to go to him. He does, and Fletcher asks again if he saw anything, also telling him quietly that if he says anything, he will beat his mother. Nullah does not say anything more, and Sarah says that maybe he was mistaken. Fletcher hands him off to the cook (Sing Song). But Nullah gets away and runs up to the windmill, which Fletcher said had not run in years. Nullah climbs up the tower and takes out a pin, and the wheel springs to life, turning on a faucet. Nullah yells that Fletcher lies. Fletcher runs after Nullah and hits him, and in the process, hits Nullahs mother and grandmother. Sarah runs over and smacks Fletcher with a riding crop, and fires him on the spot. Fletcher tells her she will not have anybody for the Drive in the morning (taking 1500 cattle to Darwin).
Sarah goes inside, and Nullah says from then on, everyone called her Mrs. Boss. She goes to Flynns place, and demands to know the truth about the Faraway Downs. He tells her that Carney has been siphoning off her cattle, and the overall state of finances, which is not good. However, if they can get their 1500 cattle to the docks to sell to the Army (before Carney), she will be set for a long time. After hearing all this, she has a drink with Flynn.
Everything starts to rumble, and they go outside to see Drover bringing in a herd of wild horses. She walks back to the house as he starts yelling about where all the men are. She explains that she fired Fletcher, and he cannot understand why, thinking she dismissed them for some stupid reason. She tells him that he was stealing cattle, and he seems a little less angry. She wants him to drive the cattle, promising her thoroughbred (used to be her husbands) to him if he helps. But he now does not have enough people to help drive the cattle. He has only three, himself, Magarri, and other aborigine, but he needs seven. We then see Nullahs mother and grandmother showing that they can ride horses. Nullah volunteers (so he has five and a quarter) and Sarah notes she can ride, too. Drover explains that it is not easy riding, but she insists. They could use one more, but the cook does not want to, and Flynn is a drunk.
The day before they leave, a car is seen driving up the road. Nullah again runs for the water tank (that has some water in it because the windmill works) and his mother follows him. Sure enough, it is the police. They tell Sarah that they think the killer of her husband is King George, and they are working to find him. They also are looking for a little boy, to which Sarah says she will keep a lookout. During this time, one of the men from the car uses the faucet to cool down. However, this fills up the water tank. Nullah and his mother cling to the ladder, but they cannot call for help, since Nullah would be taken away. The ladder breaks, and Nullah and his mother have a hard time staying afloat. Nullah tries to hold her up, but it is too hard. The car finally leaves as Drover rides up. Sarah tells him that Nullah and his mother are in the tank, and to help them. Drover gets up to the tank, and can only lift the mothers lifeless body out. Nullah is heartbroken.
That night, Drover explains that her name cannot be said again because of the aboriginal cultural, and that Nullah needs mothering. Sarah tries to say she is not good at it, but finds herself down at Nullahs. He is curled up against the wall, and wants her to go away. Instead, she asks if he wants to hear a story (after trying to offer her condolences). He is always interested in hearing stories, and she tells him a bit about the Wizard of Oz, after she sees an ad for the movie in a newspaper she is sitting on. She tells him about the twister, and sings a little bit of Somewhere Over the Rainbow and he makes connections about King George (magic man/Wizard of Oz) and the rainbow serpent.
The next morning, they are about to set out, when Sarah says to wait. The wind creates a dust devil, and Nullah calls it a twister. When it dies down, Flynn is riding a horse and ready (sober) to join the drive. They set out for a very long journey.
Meanwhile, King Carney learns that not only is Sarah not going to sell her property, but also that shes driving the cattle to the docks to sell. Carney tells Fletcher to make sure they do not get that far.
One of the nights, they drive into a canyon, and the camera shows that King George is following the group. From the top of his hill, he can see four riders approaching in the distance; it is Fletcher and 3 cronies. Nullah tells Flynn that King George is his grandpa, and asks if he knows how to play Somewhere Over the Rainbow on his harmonica, which he does. Drover makes assignments to watch the cattle and keep them calm, and Sarah makes an issue of a child working at 3am, volunteering to take his shift. But Drover will have none of it, and that is that.
When Flynn and Nullah have their shift, Fletcher and his group pour gasoline on some brush behind the cattle. They light a match, and the brush goes up in flames, creating a stampede. Everyone wakes up, and Drover realizes that the cattle are head towards the cliff. Fletcher and Flynn are closest to the front, so they take off for the cliff to try to round the cattle back towards the canyon. The others get on the horses as quickly as they can, trying to do the same. Flynn and Nullah closely navigate the edge of the cliff, trying to stay ahead of the cattle. One or two cattle slip off the side, and Nullah and Flynn are sending rocks tumbling. They make some progress, but Fletcher and his cronies have thought ahead. They lit another fire, cutting off a safe place, and spooking the cattle back towards the cliff. Flynn and Nullah are riding farther in, but all of a sudden, Flynns horse breaks a leg, sending him flying towards the ground. Nullah cannot reach Flynn before he is trampled, and the cattle are rushing at Nullah, who is at the edge of the cliff.
He then resorts to a song and magic to stop the cattle, with King George chanting from the canyon. Miraculously, the cattle stop. Nullah collapses, but Sarah catches him before he tumbles down the cliff. Drover helps console Nullah a bit before realizing that Flynn is not there. He runs to Flynn, who is bruised, bloodied, and has a leg in a rather grotesque position. He tries to keep the mood light, telling Drover that he stashed some alcohol under the wagon, and giving him his harmonica. He also tells him that Sarahs husband was killed with a glass-tipped arrow. The glass comes from the same area that King George is from; hence, it looks like King George killed the man. Flynn dies as Drover derives a conclusion. Fletcher and his cronies are a little amazed that the creamy (what they call mixed race children, among others) might actually have magic. They ride away and plot their next move.
Everyone makes it back to camp, where most of their stuff is burned. (Really, just Sarahs stuff). Sarah realizes how foolish it was to bring all of that along, and asks if Fletcher was behind it. Drover tells her what Flynn said, and that Fletcher killed her husband (using the glass-tipped arrow to put the blame on a certain aborigine), so he probably was. She says that they cannot let them win, and he replies they will not. They decide to move on in the night.
The next time they stop, they get out the rum and give a toast to Flynn (who can no longer be named). They wind up finishing the bottle. Some of the group play music and Sarah asks Drover to dance, teaching him some Foxtrot. They get close, and eventually share a small kiss. They are interrupted by Nullah, (in a tree above them), who asks if they are going to do mixed up/sideways business. Hes called down by his grandmother, and Sarah and Drover talk about their past business. Drover was married once, but he had to go to war, and when he came back, his wife had TB. But the hospitals wouldnt treat her because she was black. He did not have children, to which Sarah says is a shame because she thinks he would have made a great father. He asks her if she has any, but she tells him she cannot; he then responds the same way, telling her she would have been a great mother.
The next time they travel, they are driving across a really dry place. Magarri is at a watering hole, but he only splashes the water. The camera zooms out and there is a dead animal in the pool and one near it. He tells Drover that the water is bad. Fletcher is the one who probably poisoned it. They argue about what to do. The nearest water is a five-day ride, but Magarri remarks that across one of the deserts, a three-day ride, there is water. Drover argues that there is no way they can drive across it, because there is not enough landmarks, so theyll get lost and die. However, King George appears, and Nullah asks him to find the way to water. They follow him, and KG is shown singing and dancing his way through the desert. Drover explains that the aborigines have a song for every rock and landmark, allowing them to find a path.
The movie then cuts to Darwin, where King Carney is pressuring the Army leader, Sergeant Callahan, to sign a contract for his cattle. This cuts to a newspaper that has a story about a cattle drive across the desert that killed all the members, reportedly, including Sarah. The woman reading the story is getting her hair done, when she looks over and sees a calf in the street. She thinks it is cute and walks over to the window. Then, the teacups and everything else start to rumble and a whole herd comes running down the street. Carney and Sergeant Callahan see this; Sarah rides up and says she will accept 20 percent less than what Carney wants. Carney argues that the contract is signed, but Sergeant Callahan notes that it only applies once the cattle are on the ship. Both groups race to board their cattle first.
Sarah drives the cattle straight down the dock while Drover tries to stop Carneys cattle. He is cut off though, so instead, he rides down the wharf along with Sarahs cattle, and is able to cut off Carneys cattle , which are in a chute. He cuts the rope that holds up a stopper for the chute, stopping the cattle. Nullah drives the last steer onto the boat. Everyone regroups for a drink at the bar. Sarah walks in, and the barman again tells her that there are no ladies allowed. But a fellow at the bar says that she just drove cattle, and shes not lady and she deserves a drink. She and Drover drink a shot.
The next day, she is all cleaned up and in a dress; she goes outside to see Drover working with the horse she promised him. She tells him that he is good with horses, and that she was thinking he could manage Faraway Downs. But he is not interested, reminding her that hes a Drover, and they do not work for anyone, so no one can hire or fire him. She also tells him that she is the guest of honor at a ball the next night, and there is a suit for him, although he does not want to go.
At the ball, all the men are smitten with her. She eventually meets up with a doctor who runs the mission, and she tries to convince him to stop taking children away from their mothers. She insults the group by saying that they never ask the mothers about taking the children, and they certainly cannot ask the fathers because they are all there (men like Fletcher, et al) (The women are horrified at her accusations). In the midst of this, the first dance with Sarah (since she is the guest) is being auctioned off, and Carney offers 500 pounds. They dance and he tries to convince her to give up Faraway Downs, saying that the people who live there will be taken care of (hell put it in the contract). After the dance, she sits down, and he asks her if his lawyer should draft up the papers. However, everyones attention has turned towards the entrance. She realizes that it has gone quiet, and she turns around to see Drover, all dressed up. She tells Carney that Faraway Downs is no longer for sale.
She walks up to him and he tells her that he could not let his dance lesson go to waste. They dance, as everyone is incredulous that she would dance with him (since he associates with aborigines). They leave the ball and walk down by the docks and bar. It begins to rain and they kiss again. Everyone is out celebrating the rain, and they go back to her room and make love. At the ball, a drunken Fletcher is stumbling about, and Carney basically tells him he is worthless because he was supposed to stop the cattle and he did not. But Fletcher is also dating Carneys daughter, so he better be careful. During the ball, the rest of the group is watching a showing of the Wizard of Oz, which Nullah loves. (They have to smudge him with ash because creamy people cannot attend)
Next, it is back to life at Faraway Downs and the love between Sarah, Drover, and Nullah. Drover still goes on drives for horses, but mostly life is going well. Nullah says that King George wants him to go on a walkabout, in order to become a man. Drover tells him that Sarah is the boss, so only if she tells him he can. She does not want to let him go, but Drover argues that it is his culture. Interspersed in this part is a newspaper that says Carney died in an alligator attack. Really, the camera shows that Fletcher hit Carney into the water, and then he was attacked.
One day, Fletcher stops by to talk to Sarah. He tells her Carney died in an alligator attack, and says how dangerous it must be in the wild. She wants him to leave, but he stays longer, ultimately pointing out a display of glass-tipped arrows. However, there is one missing He leaves, and Sarah tells the grandmother not to tell Drover he was there.
In the morning (or later, time is all over the place in the movie), Sarah is distraught because Nullah is missing. She wants Drover to come help find him, but he tells her that he is safe with King George. This highlights the growing strain on their relationship, and their argument ends with her telling him not to return if he is going to be gone another six months driving cattle.
But Nullah and King George are not safe. The police and a tracker are still after him, and they are both caught. Nullah is sent to the mission and KG is put in jail.
One day, Sarah drives to Darwin; the town is being evacuated because of the growing threat of war. She is looking around, and then decides to walk down on the docks. She seems to sense someone, but she cannot put her finger on it until she hears Nullah singing (who had seemed to sense Sarah was there). She tries to get him back, but since he is part of the mission, he is being sent to an island where another mission is. The other women do not know why she is acting that way, but Fletchers wife wants her husband to do something. He tells her he will, and Sarah walks the dock and waves goodbye to Nullah, telling him she will get him back. Fletcher walks up to her and says they're taking the children to Mission Island, which is probably the 1st place the Japanese will bomb. he then says that if she'll sign Faraway Downs to him, he'll see what he can do for her & Nullah.
Sarah stays and works in the city for the Army at their radio headquarters. Occasionally she gets to see Nullah, and today is such a day. She has made friends with Fletchers wife, and they work together at the headquarters. However, the war has other plans.
The main radio for Darwin is located on the same island as the mission (I think it is actually called Mission Island). We see Japanese planes take off from a carrier and head towards Darwin and the Island. The mission boys are playing down by the ocean when they hear the planes, four of which swoop down and begin firing on and bombing the island. The rest of the planes head toward the city, where everyone is caught by surprise. One of the first places to be bombed is the Army headquarters, which just figured out that the island was probably bombed. Sarah walks toward the windows and sees the planes, and a large explosion occurs. The jail where King George is also bombed, and eventually the chief opens the door for the prisoners.
Back in the outback, Drover and Magarri are setting up camp at the same spot they did when Drover danced with Sarah. Magarri is whistling Somewhere Over the Rainbow and Drover tells him to find another song. He starts on another song that Drover knows and reminds him of Sarah, so he tells him to stop again. Magarri tells him to just admit that he still wants Sarah, and makes reference to his first wife, who was Magarris sister. They also argue a bit about Nullah, with Drover saying that he should go on a walkabout because it is culture, and Magarri says he is always hiding behind aboriginal arguments. They then see a convoy of American troops driving down the road, and they both realize that something must be wrong in Darwin, where Sarah is. They both take off for the city. Meanwhile, Sergeant Callahan is walking through a makeshift hospital and two soldiers are carrying a body on a stretcher. The person in charge of the morgue tells them the person had better be dead or dying, and he asks the name. They say Sarah Ashley, and Sergeant Callahan turns around, and asks what the man said the name was.
Drover and Magarri get to the city, and most of it is in flames. He finds someone who knows Sarah, and they tell him that she worked at the Army headquarters. He runs down there and the entire building is on fire. He wants to run in, but is stopped by Magarri and a bunch of others. He is convinced that she is in there, and must face the fact that she is probably dead. He begins walking through the city, and he thinks of all the memories of them together in various places. He makes it to the bar, gets a drink, and gets the barman to serve Magarri (who was not allowed in because he is black). Meanwhile, a priest is trying to get a boat to go the island. The barman, Magarri, and Drover go to the docks and get a sailboat and head over to the island.
Sergeant Callahan asks to see the person they are caring and he pulls the sheet back. He says there is a mistake, that the woman is Fletchers wife. At this point, Sarah rounds the corner and sees her friend, and Sergeant Callahan takes her back outside. She then wants to go to the mission, but he tells her that the place was probably bombed first.
Back at the island, Drover and the men see the place is in flames. They fear the worst, and slowly walk towards the burning houses. But they hear noises in the bush, and out come most of the children. Nullah calls out from behind him and Drover hugs him. Nullah asks if Mrs. Boss came too, but Drover tells him that they cant say her name anymore. (Implying she is dead, since they are not supposed to say the names of the deadjust in case you did not remember from the beginning) They are about to head towards the boat when a spotlight starts to light up the hill around them. Japanese troops are moving in, so they will have to swim out silently to the boat. They make it to the water, but it is unlikely they will get to boat without being seen. Magarri tells Drover to get the kids to the boat, and he will distract the troops. He takes a gun and fires some shots at the troops as the rest make it to the boat. Magarris gun jams, so in order to keep the others safe, he runs down the shore, but is shot in the back. The Japanese finish him off as Magarri watches the boat float silently away.
In the morning, the Army is packing up the troops and any civilians and pushing farther inland. The last caravan is leaving and Sarah is hesitant to leave. The camera shows the boat is almost to the docks, as it is navigating around destroyed ships. Sarah is about to get in the truck when she hears a harmonica playing music. Its Nullah on the front of the boat, and the rest of the children eventually join in singing. She keeps hearing it, so she runs toward the docks. As the smoke clears and the boat comes closer, she sees Nullah and the rest. Nullah runs up the dock and gives her a big hug, saying he sung her to him. She asks how they got back and he just smiles and looks down the dock; she turns around and there is Drover. He is amazed she is alive, and they hug. The rest of the children come up, and Sergeant Callahan loads them up into the caravan. Sarah, Drover, and Nullah embrace, and Sergeant Callahan tells them Faraway Downs is probably going to be safe.
Drover goes to the bar to get something while Sarah is on the docks. Nullah is walking in the space between. The camera shows Fletcher walking around, despondent over everything, from his place being bombed, to losing his wife. One of his old cronies comes up to him as he sees Nullah running around, and Fletcher takes his gun, telling the guy to find the police chief to say there is looting. During this time, King George has been watching events unfold from a water tower. He sees Nullah running and Fletcher beginning to take a position. KG starts ripping a section off the tower. Sarah senses something is wrong and yells at Nullah, and starts to run towards him. Drover looks back from the bar and can see Fletcher aiming a gun at Nullah. He runs from the bar to protect Nullah. A shot rings out as Drover reaches Nullah.
Fletcher is shown holding the gun, ready to take another shot. But King George throws a spear at him, impaling him, saying, He is my grandson, and your son.. Fletcher dies, slumped over a pile of rubble. The police chief finds him, and looks at the water tower, but KG is gone.
Drover is holding Nullah, telling him to wake up, and he does. He tells Drover he is ok, that there was no bullet.
The family is headed back to Faraway Downs when they stop for the night, again at the place where they danced. Everyone is collecting firewood when Sarah looks back and sees King George. He beckons Nullah, and Sarah kisses him goodbye before he runs off.
The final screen tells us that Australia finally ended their Stolen Generations policy in 1973. In 2008, the Prime Minister issued a formal apology for the governments actions.