Ben is at first separated from Ned, previously known as Den, when their adrift boat is found by slave traders, who throw Ned overboard, because he is a black dog, which they think is a sign of the Devil. Ben is taken to Al Misurata, while Ned is found by a wandering troupe of entertainers that nurse him back to health. Among them is the beautiful Serafina, who sings like an angel. Ben and Ned are reunited when Al Misurata has the troupe perform for him, and Ned has been incorporated into their act. Ben also falls in love with Serafina, who returns the affection.
Ben and Ned find out while staying with Al Misurata that he plans to sell the troupe into slavery, under the guise of returning the troupe to Italy. While on his ship, the Sea Djinn, Ben and Ned jump overboard to escape, with the intention of rescuing their friends. As they reach land, they see a young boy named Joshua who is about to be attacked by sharks. They save him, and find out that the boy is the grandson of a Jewish sailor/warrior, who pledges to help the two in anything they might require aid with. They ask only to be taken to Italy. After saving his grandson, he quite willingly obliges. Once they reach Italy the boy and his faithful dog set sail once again for their destination with a friendly Greek sea captain. After another adventure, they finally rescue the troupe, and take shelter in a convent. Unfortunately, Al Misurata finds them, and in the struggle, Ben is stabbed in his shoulder. Al Misurata, his second-in-command Ghigno, and Serafina fall to their deaths over a cliff. Overwhelmed by sadness at the loss of his wonderful friends, the ancient boy and dog flee to the sea to get away from sorrows, and continue their eternal journey on the Blue Turtle.