Ivan, nearly eleven, and Marianna, twelve, find themselves in a miniature world when they shelter under a bush on a rainstorm. When Ivan brags about his city home, Magellan, a winged equus (please don't call him a horse), and Paracelsus, an ancient and slightly hard-of-hearing dragon, are convinced that the boy is describing the fabled city of Mythaca. As soon as Paracelsus gets the spell right and the children are small enough to ride on the backs of the mythical creatures, the four are off on an unforgettable quest.

The children are listening to the passed-down tales of Mythaca and its inscrutable antagonist, Maya, when Marianna discovers that she is growing wings. Unfortunately, the effects of the fruit that must have caused the transformation are unpredictable, and the wings shrivel up and disappear at the wrong moment. Soon the travelers are separated, and Magellan and Ivan fall into one of Maya's traps. The travelers eventually meet at the woodland workshop of Icaria, flying cat and featherer, who tries to fit the girl with artificial wings. Photinus Pyralis, a glowing creature from another world, asks each of the travelers to draw what wisdom they can from their adventures before presenting them with gifts. Magellan, Paracelsus, and Icaria receive some duct tape, a penknife, and a mysterious tool with a spinning disc at its end. Ivan is given a perspectus, a sort of helmet that will let him see from the point of view of anyone or anything once he learns to use it; Marianna gets the gift of languages, which, with some practice, will let her to understand the language of anyone or anything. The rest of their journey is not as easy as they hope. The group is again separated, there are riddles and paradoxes to resolve, and peace, both internal and external, to be made, before the portal to Mythaca will open.

Full of gentle humor and wisdom, Journey to Mythaca is a story about stories, set at the border between belief and reality. When Ivan loses patience with Paracelsus's tales of Maya, he cries out, "Why should I believe you? Have you ever seen her? Everything you know is just stories!" to which Paracelsus replies mildly, "Stories? It's all stories, Ivan. Our lives are stories. We live stories." In the end, beyond the uncertainty of not-knowing that that understanding brings, the children discover that some things, such as music, love, and friendship, have magical power in all the worlds they visit.