Although they lie 16th in the Bundesliga, Stuttgart are now among the best 16 teams in Europe and are in the draw for the next round after getting off to an electric start that left Dan Petrescu-coached Urziceni stunned.
Former Tottenham Hotspur coach Gross took charge of Stuttgart on Sunday after Markus Babbel was sacked because his side won just twice in their last 15 Bundesliga matches.
But Romanian striker Ciprian Marica, Christian Träsch and Russian forward Pavel Pogrebnyak all scored for Stuttgart in the first 11 minutes as the home side effectively ended the contest by racing into a 3-0 lead.
Portuguese winger Antonio Semedo pulled a goal back for the Romania champions almost immediately after the half-time whistle, but it proved to be no more than a consolation goal.
The win sees the Germans leap-frog the Romanians to finish second in Group G behind winners Sevilla.
"I tried to be very goal and result orientated right from the start and I said right away on Sunday that we needed at least two goals," said Gross. "The morale is low on account of our table position, but the Champions League is the best tournament in the world and everyone can show what they are made of in it."
But while Stuttgart join Bayern Munich in the draw for the last 16 on December 18, Gross still has his work cut out to get his side out of the Bundesliga's bottom three.
"I was happy to come to Stuttgart although I am fully aware of how hard it will be," he admitted. "I was only asked to take over the job at the weekend."
Ex-Germany goalkeeper Jens Lehmann, who turned 40 last month, admitted he was delighted to see Stuttgart make the knock-out phase before he retires at the end of the season.
"That was a fantastic start and it was great to take a 3-0 lead so quickly," said Lehmann, who has plenty of Champions League experience from his five years with Premier League club Arsenal.
"We were hot, we were concentrated and we weren't so nervous. It was good motivation to qualify for the best club competition in the world,” he added.