Misfits & Heroes: West from Africa, by Kathleen Flanagan Rollins, takes place around 12,000 BC, and as you may have guessed, starts off in Africa. Naaba is an outcast from his village and a wanderer. It has been a long time since he's been part of a village, so when he comes upon one, he is drawn to it and watches a weaver at her work. While in this village, he finds Asha, a woman being held captive, and he frees her. She is drawn to water, and follows it even when it cannot be seen, and she decides to join Naaba in his wandering, so that she may follow the water without being punished.
Naaba and Asha follow the river until they see a circle of standing stones. Naaba especially is curious, and this is the point where the book really takes off. Naaba and Asha fall in with a group of people and become a part of something that will change forever the course of everyone's lives. The Black Rhino, a power-hungry leader, has a grand vision of uniting all the people and all the villages as one. The campaign to bring this into being, however, is violent, and opposition is not met with in a diplomatic way. One of his main concerns is another leader, Dwyka, the She-Eagle, and it is between these forces and the conflicts that arise that Naaba and Asha find themselves. They know they must find a new place. They become thrown together with a group of people, some they are familiar with, and some strangers, and they all set off together down the river and out into the sea, where none of them have ever been.