In the twenty-fourth century, an unusually productive group of researchers develop both time travel and immortality. With cheerful hubris, they create a company named "Dr. Zeus, Incorporated" and proceed to take over the world. (This conquest seems less far-fetched when one considers what Microsoft accomplished with just a second-rate operating system and shrewd marketing policy.)

Once Dr. Zeus has conquered the present, the next target for takeover is the past. The nature of time travel prevents them from altering recorded history, but unrecorded history is fair game. The immortality process only works on young children, so children in each era who would have died or disappeared are recruited into the ranks of immortal Company agents and stuffed full of circuitry that give them superhuman strength, speed, and senses. All this setup results in a secret network of agents with modern sensibilities and a severe sense of their own superiority.

Mendoza is recruited at four years old from the dungeons of the Spanish Inquisition. At seventeen, with a twenty-fourth century education and a hearty contempt for mortals, she is sent to England during the reign of Bloody Mary to preserve samples of a rare species of holly from the garden of Sir Walter Iden. Her task is made more difficult by her percolating hormones and the presence of Sir Walter's secretary, Nicholas Harpole, an attractive mortal with nice legs, a ready intellect, and religious opinions that could get him burned as a heretic.

Comparisons to Connie Willis's Doomsday Book are inevitable; both feature time travel, English history with tremendous period detail, and a heavy-handed message about the fleeting tragedy of life. In the Garden of Iden has more sarcastic narration and a greater focus on religious and racial intolerance.

Baker never explicitly describes the immortals' range of powers, which is occasionally confusing, but she very cleverly slides her Company agents into the role occupied by the Faerie in myth: immortal, dangerous, and aloof, with designs beyond mortal ken. In the Garden of Iden is a sharp, clever story and a very strong first novel.