The description—especially as expanded in the comments by tbrookside—sounds a lot like “The Allies”, by Mark S. Geston. I’ll give a little more detail so you can confirm, but of course, that will mean some spoilers. I’ll try to keep the spoilers to the bare minimum beyond those revealed in the question and comments.
The story opens in the middle of an alien invasion by a single-minded but ruthless species that seems intent only on eradicating humanity and all its traces, but otherwise doing no damage whatsoever to the Earth.
It had become obvious how greatly they prized our world and everything on it but us by the fifth year of our conflict. Their weapons were normally used with economy and dismaying accuracy so that nothing but humankind and our works were destroyed. Fusion weapons were directed against the great cities, but never where their shock waves would escape built-up areas. That was thought to have been why New York was never bombed, out of concern for the green expanse of Central Park. Surface darts were sent to cut all the bridges, pipelines and cables, and fly down the entrances to the river tunnels. The city was effectively besieged and starved into submission in a month.
Not only did the aliens take great pains to avoid harming the natural world during their genocidal campaign against humanity, they also restored all the areas they conquered back to their pristine natural state. And the animals were starting to act strangely.
Great care was taken to understand what was going in the occupied territories: how many extinctions were averted, how many rare species suddenly brought back to Edenic plentitude, how many thousands of square kilometers of forest reclaimed, dams removed, highways torn up and the ground resown, cities leveled and the places where all the people had been murdered turned into gardens. What was similarly noticed but much less talked about was how impoverished our remaining lands became. What few animals remained with us either sickened and died or just vanished when we were not looking. Either that, or they were the targets of rage and frustration and were the subject of eradication campaigns. Thus, the pigeons and starlings were erased from New York before its siege and all the squirrels in Boston were killed in one July. After the fifteenth year, it seemed like the only animals left were those held captive in zoos or the few anachronistic farms that depended on such things.
“When was the lat time I saw a bird?” my father asked me shortly before he died. “Just a crow or a seagull? When? A year? Five? Is that possible?” He was not looking at me, but all around at the sky, as if he had misplaced these creatures on a neglected atmospheric shelf and forgotten them.
Realizing they were going to lose the war, and likely be exterminated, humanity builds several escape ships using stolen alien technology. The story is narrated by the Captain of the last ship.
They successfully escape, and for an unspecified amount of time in Earth’s frame of reference—but only a few years ship-time—they wander the galaxy searching for a new world to settle, but find nothing suitable. Eventually, with tensions on the ship rising, they decide to take the risk and return to Earth.
On returning, they discover that all signs of human presence have been completely excised. Even the radioactive trace elements you’d expect are gone. The Earth has been returned to a state of natural paradise, and animals that were on the verge of extinction are thriving. Even some new species have begun to evolve.
With only one curious exception.
The day before we landed, I asked the Minds if there was any sort of life that had been present before we left that was not there in profusion now. The Minds, who were preoccupied with preparations for the landing, tried to brush me aside. They impatiently said that it was irrelevant, but I persisted. After more argument, and becoming unaccountably more anxious to have the question answered, I invoked rank and ordered them to respond.
An hour later, irritated voices hissed from the open doors of the Palace’s ballroom that it would be impossible to do much of a survey of anything lower than vertebrates, even incorporating all the observations they had gathered from the past two objective months in orbit. Then they told me that the only ones missing were the dogs. The closest members of the family they could locate were isolated populations of coyotes and wolves in the high latitudes of the northern hemisphere, and most of them seemed to be suffering from disease and malnutrition. The Ship’s Minds did not attach any significance to this.
The ship lands, and the humans immediately begin to notice the strange behaviour of the animals.
Antelope! And buffalo behind them. Look! Prairie kites were riding the thermals, as if we had never flown through their sky. I hoped I was not being undignified, but everyone around me seemed to be thinking the same thing, smiling and laughing to themselves and pointing at the antelopes, now only a hundred meters away.
I had forgotten the context of their beauty; they were creatures from memories inherited from grandparents. Tan and sable with black markings on skins stretched tautly over bodies designed to run for days over the grasslands. The Minds remarked that the creatures were moving in uncharacteristic ways that suggested they had been improved during our diaspora, and then fretted over whether they were concealing new abilities of thought and organization.
I stopped ten meters from the lead buck to see if they were going to run away. Instead, this animal merely stared at me with extraordinary eyes until I began to imagine that there really was some new and subtle intelligence behind his gaze. Four other animals symmetrically positioned themselves behind him, two on either side. They were larger than I had anticipated and someone behind me asked permission to arm his weapon.
As if it had overheard, the lead animal turned carefully and began walking away. Once he was past them, his four companions followed, and then the rest of the herd fell in behind, aligned in what might have been imagined as columns of march. Stood where I was signaled everyone else to stand still. The Ship’s Minds were watching and would tell me if this was anything more than the unconcerned withdrawal of animals who had never seen people before and whose conceptions of space were too limited to appreciate the Ship’s presence.
I personally thought their look and pace to be utterly contemptuous. They remembered precisely who we were, what we had done and how we had lost the struggle for this place.
The humans begin to resettle the Earth, despite the strange behaviour of the animals, who all seem to go out of their way to avoid them completely. The narrator—the ship’s Captain—instead focuses on the mysteries underlying their situation:
- Why were the animals behaving so strangely?
- What happened to the alien invaders?
- Why were only the dogs missing?
The investigation and its conclusions shake out roughly as described in the question and comments: A fox is found, and tells the majority of the story and provides other clues (!), and it turns out the dogs ended up fighting on our behalf (though why that happened is one of the story’s primary themes), and that the rest of animalkind despises them for it. There are some differences in the details that are really important to the story’s theme, and I don’t want to spoil them, but the gist of everything mentioned in the question and comments is pretty much spot on.
The only thing that doesn’t quite match is your recollection of the ending. That line or something similar may exist in the story—it would sure fit a lot of places, but I don’t think it’s anywhere near the end because it doesn’t quite match the tone of the final bit. The story’s ending isn’t quite that bleak; it’s actually quite bittersweet, though open-ended. It’s less “our past paradise is forever lost to us” and more “it will be harder this time around, but maybe we a chance to do it right this time”.
It was originally published in The Magazine of Fantasy & Science Fiction in 1998, and appeared in 1999’s Year’s Best SF 4, edited by David G. Hartwell.
