A million years prior to the dawn of Homo sapiens, two immortal, shapeshifting aliens, wholly unknown to each other, roam the Earth without memory of their origin or their purpose.
Both immortals seek each other for different reasons: one harbours good intentions toward humanity and wishes to protect all life, while the other is extremely hostile and enjoys killing.
He is approached by elderly Admiral Jack Halliburton, who has a for-profit job for Poseidon: recover a submarine sunk in the Tonga Trench, and then "find" a mysterious cigar-shaped object located nearby.
In 1935, the changeling attends the University of Massachusetts to study oceanography, then the Woods Hole Oceanographic Institution; it senses that something important to it will be found in marine science.
In 1941, it takes part in the Bataan Death March, during which "Jimmy" sees horrific incidents which humanize the changeling; it learns friendship and pity.
The changeling escapes Bataan and spends years swimming back to America as a shark; meanwhile, the chameleon enjoys war atrocities and becomes assistant to Josef Mengele at the Auschwitz concentration camp.
The team plunges the artifact into different atmospheres – specifically, those of the planets and moons of our Solar System – in case the object might recognize one of them as "home-like" and respond.
At last, her spaceship traps "Jack," and, revealing her true self (large, shimmering, colorful, "inhumanly beautiful"), she tells Russ that she must return home.
One juror, Ursula K. Le Guin, wrote in her decision, "An ageless, sexless entity who can take any form is at first indifferent to gender; as it grows more human, the choice becomes more important to it; it ends up a woman by preference.
Another juror, Cecilia Tan, wrote, "Haldeman is a Hemingway scholar, and it shows in the elegance of his minimalist prose in this thought-provoking book.
Library Journal wrote, "With his customary economy of words, Haldeman (The Forever War) examines the differences and similarities between human and nonhuman nature as his protagonists face possible destruction.
"[4] Booklist wrote, "Award-winning sf veteran Haldeman proves as engaging a storyteller as ever, especially given this book's irresistible premise and page-turning action.
"[5] Entertainment Weekly gave the book a B+ grade: "Haldeman trips through history wearing alien goggles, but his message is all about human nature."
)[6] Gerald Jonas of The New York Times Book Review said, "Haldeman handles this complicated scheme effortlessly, and the ending is satisfying whether or not you have figured out who is who.
"[7] The San Diego Union-Tribune wrote, "Sometimes grim, always interesting, Camouflage is written with all of Haldeman's characteristic toughness, care and clarity.
"[10] The Denver Post said, "Joe Haldeman writes a classic tale of aliens with a smooth, simple brilliance that is a joy to read.
Haldeman throws in an extra alien for no apparent reason, and the love affair that supposedly wraps up the action is neither solidly developed nor particularly believable.
"[14] Similarly, Publishers Weekly wrote, "Joe Haldeman's Camouflage, a near-future SF thriller that alternates between the experiences of two different aliens who land on Earth, skillfully weaves its disparate plot threads until the cop-out, deus ex machina ending.
"[15] Kirkus Reviews also had a mixed reaction: "Well-constructed and intriguingly set up, but ultimately a disagreeable surprise: the story slips away, and you're left holding an empty coat.