This animated feature tells the story of a convict child, Toby Nelson, who has been transported to Australia. The narrative begins in the present when an artist, who has failed to sell any of his paintings at a funfair, begins to tell his granddaughter about the origins of his paintings. The story is then told from the past, beginning with Toby's time aboard the British convict ship taking him and his fellow prisoners to New South Wales. Among the group of convicts we meet are Polly Nelson (Toby's older sister), 'Dipper' Davey (an old pick-pocket), Big George (a blacksmith), Jack Doolan (a highwayman), and 'Silly Billy' (a village idiot).
After arriving in the colony, the five men are selected to do hard labour for the military under the supervision of Sergeant 'Bully' Langden and Corporal 'Weasel' Wesley, while Polly (secretly in love with Big George) is sent to work as a servant girl at the governor's home. In the meantime, Toby saves a baby koala, after Bully and Weasel kill its mother while hunting, and keeps it as a pet, naming it Yo-Yo. When Bully's continuing abuse of the convicts ends in old Dipper's death, Jack Doolan escapes and Big George is thrown in jail for helping him. Left with only Yo-Yo to keep him company, Toby sets out to find Jack Doolan in order to free Big George. Along the way, he meets an Indigenous Australian boy named Whooranga, who has a strange power over animals. Together with Jack Doolan, they plan a daring rescue attempt for Big George.