Voldemort was already gathering Death Eaters and was known as Voldemort by the time he was in his 6th year, as we see in The Chamber of Secrets.
"Voldemort,” said Riddle softly, “is my past, present, and future, Harry Potter…”
He pulled Harry’s wand from his pocket and began to trace it through the air, writing three shimmering words:
TOM MARVOLO RIDDLE
Then he waved the wand once, and the letters of his name rearranged themselves:
I AM LORD VOLDEMORT
“You see?” he whispered. “It was a name I was already using at Hogwarts, to my most intimate friends only, of course."
And in The Half Blood Prince:
Tom Riddle merely smiled as the others laughed again. Harry noticed that he was by no means the eldest of the group of boys, but that they all seemed to look at him as their leader.
We also see that his followers are openly the 'Death Eaters' and that he has started to do evil things by the time he applies for the Defense Against the Dark Arts position, as we see in Dumbledore's memories:
Dumbledore raised his eyebrows. "And what will become of those whom you command? What will happen to those who call themselves - or so rumor has it - the Death Eaters?"
Harry Potter and the Half-Blood Prince, chapter 20
The name being feared probably happened gradually, as his reign of terror got worse. The more evil things he did, the more people feared him = more people feared his name. But it probably wasn't all at once; it happened gradually.