"All the Way Back" by Michael Shaara (Pulitzer prize winning author of The Killer Angels), first published in Astounding Science Fiction, July 1952, available at the Internet Archive. The text of the story is also available here. Here are some excerpts to show how it matches the description in the question:
So the story goes, humans in a spaceship search for an inhabitable planet, being surprised they found none in the vicinity of Earth.
The ship had been in deep space with her ports thrown open. Absolute cold had come in and gone to the core of her, and it was always a while before the ship was reclaimed and her instruments warmed. Even now there was a sharp chill in the air of the cabin.
Jansen sat down idly, rubbing his arms.
"Last time around, I guess."
"Yes," said Cohn, and added laconically, "I wish Weizsäcker was here."
Jansen grinned. Weizsäcker, poor old Weizsäcker. He was long dead and it was a good thing, for he was the most maligned human being in the System.
For a hundred years his theory on the birth of planets, that every sun necessarily gave birth to a satellite family, had been an accepted part of the knowledge of Man. And then, of course, there had come space flight.
Jansen chuckled wryly. Lucky man, Weizsäcker. Now, two hundred years and a thousand stars later, there had been discovered just four planets. Alpha Centauri had one: a barren, ice-crusted mote no larger than the Moon; and Pollux had three, all dead lumps of cold rock and iron. None of the other stars had any at all. Yes, it would have been a great blow to Weizsäcker.
They find one,
For reasons which were as much sentimental as they were practical, they started with the third planet of this fruitful sun. There was a thin atmosphere, fainter even than that of Mars, and no oxygen. Silently they went on to the fourth. It was cold and heavy, perhaps twice as large as Earth, had a thick envelope of noxious gases. They saw with growing fear that there was no hope there, and they turned quickly inwards toward the warmer area nearer the sun.
On the second planet—as Jansen put it—they hit the jackpot.
A warm, green world it was, of an Earthlike size and atmosphere; oxygen and water vapor lines showed strong and clear in the analysis.
and it seems uninhabited.
"No people at all. It's ours." And after a while Jansen said: "New Earth. That's a good name."
At the same time are observed by the aliens, who go down on the planet to meet them.
Roymer was now clearly worried. He turned away and paced the deck for several moments. Abruptly, he left the room and went to the files of alien classification. He was gone for a long time, while Goladan fidgeted and Trian continued to gather information plucked across space from the alien minds. Roymer came back at last.
"What are they doing?"
"They are moving in on the second planet. They are about to determine whether the conditions are suitable there for an establishment of a colony of their kind."
Gravely, Roymer gave his orders to navigation. The patrol ship swung into motion, sped off swiftly in the direction of the second planet.
The aliens sit them down and tell them a story about war and conflict that ruled the galaxy, and how all the sentient races in the galaxy got together and got rid of the race that tried to conquer all by blowing up their planets.
"The news of what happened to the Apectans set the Galactic peoples up in arms, but it was not until the Antha attacked a Federation world that we finally moved against them. It was the greatest war in the history of Life.
"You will perhaps understand how great a people the Antha were when I tell you that they alone, unaided, dependent entirely upon their own resources, fought the rest of the Galactics, and fought them to a standstill. As the terrible years went by we lost whole races and planets—like this one, which was one the Antha destroyed—and yet we could not defeat them.
"It was only after many years, when a Galactic invented the most dangerous weapon of all, that we won. The invention—of which only the Galactic Council has knowledge—enabled us to turn the suns of the Antha into novae, at long range. One by one we destroyed the Antha worlds. We hunted them through all the planets of the desert; for the first time in history the edict of the Federation was death, death for an entire race. At last there were no longer any habitable worlds where the Antha had been. We burned their worlds, and ran them down in space. Thirty thousand years ago, the civilization of the Antha perished."
Roymer had finished. He looked at the Earthmen out of grave, tired old eyes.
In the end you realise man is this terrible conqueror the aliens are talking about.
"Are you sure you got all of them?"
"No. Some surely must have escaped. There were too many in space, and space is without limits."
Jansen wanted to know: "Have any of them been heard of since?"
Roymer's smile left him as the truth came out. "No. Not until now."
There were only a few more seconds. He gave them time to understand. He could not help telling them that he was sorry, he even apologized. And then he sent the order with his mind.
The Antha died quickly and silently, without pain.
