Im September 1939 reist Lady Sarah Ashley (Nicole Kidman) trotz des Krieges von England nach Australien, um dort nach dem Rechten zu sehen und ihren Ehemann Maitland (Anton Monsted) zum Verkauf der unprofitablen Rinderfarm Faraway Downs im nördlichen Outback zu überreden. Gleich nach der Ankunft in der Hafenstadt Darwin muss sie entsetzt mit ansehen, wie ihre Koffer bei einer Prügelei aufplatzen und ihre Dessous herumfliegen.

Anstelle ihres Ehemanns holt der selbstständige Viehtreiber Drover (Hugh Jackman) sie in Darwin ab. Im Wohnhaus der Farm liegt Maitland Ashley tot auf dem Küchentisch. Er wurde mit einem Speer getötet. Deshalb, so der Verwalter Neil Fletcher (David Wenham), halte er einen Medizinmann der Aborigines, der sich King George (David Gulpilil) nennt, für den Mörder.

In der Nacht steht plötzlich ein Junge in Sarahs Schlafzimmer. Der Mischling ist zwölf Jahre alt und heißt Nullah (Brandon Walters). Er habe sie herbeigesungen, sagt er. Und er behauptet, Fletcher sei ein Betrüger, arbeite heimlich für den Rinderbaron King Carney (Bryan Brown) und habe Vieh aus dem Besitz der Farm veruntreut.

Als Neil Fletcher die Lady am nächsten Morgen nach Darwin zurückbringen will, stellt sie ihn zur Rede. Der Verwalter tut die Beschuldigungen als Hirngespinste eines Jungen ab. Außer Hörweite Sarahs droht er Nullah, er werde dessen Mutter etwas antun, falls er die Beschuldigungen aufrechterhalte. Nullah läuft weg. Fletcher holt ihn ein und verprügelt ihn und dessen herbeigeeilte Mutter, bis Sarah den Verwalter mit der Reitgerte ins Gesicht schlägt. Aufgebracht wirft sie Fletcher hinaus, und er verlässt mit seinen Männern die Farm.

Der alkoholkranke Buchhalter Kipling Flynn (Jack Thompson) bestätigt Nullahs Behauptung, dass Fletcher heimlich für Carney gearbeitet habe. Vermutlich sei es seine Aufgabe gewesen, die Farm herunterzuwirtschaften, um Lord Ashley zu zwingen, das Land dem Rinderbaron zu überlassen. Flynn rät Sarah, die Rinderherde nach Darwin zu treiben, sie dort der Armee zu verkaufen und dadurch Carneys Monopol zu brechen.

Doch wie soll Drover mit seinen zwei Helfern einen Treck mit 1500 Rindern durchführen? Dazu hätte er Fletcher und dessen Männer gebraucht. Sarah überredet ihn, es mit ihr, Flynn, Nullah, dessen Mutter, einer weiteren Frau und einem asiatischen Farmarbeiter zu versuchen.

Bevor sie aufbrechen können, kommt Polizei angefahren. Nullah versteckt sich mit seiner Mutter im Wassertank, denn junge Mischlinge werden in kirchlichen Erziehungslagern eingesperrt. Sergeant Callahan (Tony Barry) hat von Fletcher erfahren, dass sich ein Mischlings-Junge auf der Farm aufhält. Den Bestimmungen gemäß will er ihn abholen. Er muss allerdings unverrichteter Dinge wieder abfahren, weil er Nullah nicht findet. Als das Auto am Horizont verschwindet, zieht Drover Nullah und dessen Mutter aus dem Wasser, aber die Frau ist ertrunken.

Bei der Toten handelt es sich um King Georges Tochter; der Medizinmann ist Nullahs Großvater.

Die Luftaufklärung meldet einen Rindertreck. Carney erfährt davon, und Fletcher bricht mit drei Kumpanen auf, um den Treck zu stoppen. Mit einem gewaltigen Feuer lösen sie eine Stampede aus. Die Rinder rennen auf ein Kliff zu. Flynn stürzt vom Pferd und gerät unter die Hufe. Nullah reitet los, stellt sich vor den Abgrund, blickt die Rinder an und beginnt zu singen. Damit bringt er die Tiere zum Stehen.

Sterbend macht Flynn Drover darauf aufmerksam, dass der Speer, mit dem Lord Ashley getötet wurde, eine Glasspitze hatte. Drover weiß, dass Aborigines keine solchen Speere verwenden und ahnt, dass Fletcher der Mörder ist.

Der hat inzwischen die einzige Wasserstelle in der Nähe vergiftet. King George taucht auf und lotst den Treck zu einer drei Tage entfernten anderen Wasserstelle in den Outbacks.

Gerade als Captain Dutton (Ben Mendelsohn) und King Carney in Darwin einen Vertrag über eine weitere Viehlieferung für die Armee unterschreiben, erreicht der Treck die Stadt. Weil der Vertrag erst gültig wird, wenn die Rinder auf dem Schiff verladen sind, kommt es nun darauf an, wer schneller ist. Drover und Sarah schaffen es.

Statt nach England zurückzukehren, will Sarah die Farm Faraway Downs mit Drover als Verwalter weiterführen und Nullah adoptieren. Drover zögert, sagt jedoch am Ende zu. Er schläft mit Sarah. Die beiden haben sich verliebt, ohne es sich einzugestehen. Drover leidet noch unter dem Verlust seiner Ehefrau. Sie war eine Aborigine, die Schwester seines Freundes Magarri (David Ngoombujarra), und sie starb an TBC, während er beim Militär war.

Neil Fletcher stößt King Carney ins Wasser, wo dieser von einem Krokodil getötet wird. Dadurch erbt Fletcher den Besitz, denn er ist der einzige Sohn des Toten. Nach wie vor will er Sarah die Farm abjagen. Um sie einzuschüchtern, deutet er an, dass er Carney und ihren Mann ermordete. Sie bleibt unnachgiebig. „Stolz bedeutet nicht Macht“, sagt er mehrmals.

Während Drover fort ist, kann Sarah nicht verhindern, dass Nullah von der Polizei festgenommen und in ein Lager der Kirche auf Mission Island gebracht wird. Fletcher bietet ihr an, den Jungen von der Insel zu holen, sobald sie ihm den Besitz vertraglich überschrieben habe.

Als Drover zurückkommt, brennt es überall. Die Japaner haben Australien angegriffen. Es sieht so aus, als sei Sarah in den Flammen umgekommen. Er erfährt, dass Nullah auf Mission Island verschleppt wurde. Dort lebe vermutlich niemand mehr, heißt es, weil die Japaner die Insel wegen des Leuchtturms bombardierten. In der Hoffnung, Nullah doch noch retten zu können, kapern Drover und Magarri, der Wirt Ivan (Jacek Koman) und ein Geistlicher ein Schiff. Tatsächlich haben Nullah und einige andere Jungen den Angriff überlebt und sich versteckt. Während sie zum Schiff schwimmen, opfert Magarri sich und lenkt die japanischen Soldaten ab, bis sie ihn erschießen.

Während das Schiff nach Darwin zurückkehrt, flieht dort die Bevölkerung mit dem letzten Militärkonvoi vor den Japanern. Ein Offizier mahnt Sarah zur Eile, aber sie hört Kinder singen und läuft zum Kai. Während die geretteten Kinder bis auf Nullah zu den Lastwagen laufen und mit den anderen abfahren, fallen sich Sarah, Drover und Nullah in die Arme. Statt sich dem Konvoi anzuschließen, wollen sie zur Farm.

Fletcher, dessen Ehefrau Catherine (Essie Davis) bei einem Angriff der Japaner ums Leben kam, ist auch nicht bei den Flüchtlingen. Er entreißt einem Soldaten ein Gewehr und legt auf Nullah an. Aber er trifft nicht, denn in dem Augenblick, in dem er abdrückt, wird er von einem Speer durchbohrt. King George hat auf seinen Enkel aufgepasst. Den Sterbenden klärt er darüber auf, dass er beinahe seinen eigenen Sohn getötet hätte.

Sarah, Drover und Nullah kehren nach Faraway Downs zurück. Kurz darauf taucht King George in der Nähe auf und ruft seinen Enkel, um mit ihm das Land zu durchwandern. Sarah sieht ein, dass sie den Jungen nicht vereinnahmen kann und verabschiedet sich weinend von ihm.