The result also meant that France became the first team to secure a berth in the last eight after a scrappy 68-64 success against Turkey earlier on Wednesday stretched their perfect record to six wins.
Having carried two wins against Serbia and Germany from their preliminary pool into the second group stage, France top Group E with three wins ahead of Lithuania and Spain who have two wins and one defeat each.
Serbia and Turkey have one win and two defeats apiece while Germany are winless and face an uphill battle to finish in the top four who will advance to the quarter finals.
Group F, including the other six teams vying for the other four berths in the last eight, starts on Thursday when upstarts Macedonia and Georgia play each other, Russia take on surprise package Finland and Slovenia meet 2005 champions Greece.
Roared on by a capacity 11,000 home crowd in the Siemens Arena, Lithuania produced their best performance of the tournament and blew away 2009 runners-up Serbia.
They led from start to finish, as Valanciunas, who steered Lithuania to the under-19 world title earlier this year, poured 18 points after making eight of his nine shots from the field.
Point guard Mantas Kalneitis led the winners in scoring with 19 points and seven assists, hitting five of seven attempts from three-point range, while veteran Sarunas Jasikevicius scored 14.
"The game was hard, we played with emotions and I want to thank our fans because we felt like having a sixth player on the court," Valanciunas told a news conference.
"The assists and the number of three-point shots we converted made the difference," he said. "I feel very well with this team and when I feel well I play well."
Normally a strong defensive team, Serbia had no answer to Lithuania's quick transition from one end of the court to the other which generated a staggering total of 25 assists and 11 three-pointers from 20 attempts.
Pau Gasol missed Spain's shock defeat by Turkey on Monday with an ankle injury and struggled in the first half against Germany, having failed to score in two cagey quarters littered with fouls and turnovers.
But the Los Angeles Lakers centre battled through the pain in the second half and hauled 19 points to go with seven rebounds, keeping his perennial NBA rival Dirk Nowitzki at bay in the process.
Nowitzki, who drove the Dallas Mavericks to the 2011 NBA title, also had 19 points and seven rebounds but made only seven of his 17 shots, missing most of them when he was guarded by Gasol.
"I am still suffering a bit with my ankle but overall I felt good today, the fact that it felt a lot stronger when the game started gave me a bit of confidence," Gasol told Spanish television.
"We struggled in the first half and weren't able to hold on to our advantage, but from there on we played good defence and a day's rest will be welcome for me and my ankle," he said.
France were also unconvincing against the Turks as their top players showed the first signs of fatigue in a gruelling tournament, where teams who reach the knockout stage will have played 11 games in just 19 days.
Turkey made a bright start with a 10-2 run but soon caved in to an iron-clad French defence, which forced 16 turnovers from their opponents who also missed 19 of 24 three-point attempts.
"We missed seven or eight open shots and survived a late scare as we relaxed a bit too much, but in the end we won a great game of basketball," said France coach Vincent Collet.
The winners and the runners-up of Eurobasket 2011 will qualify automatically for the 2012 Olympics in London along with hosts Britain, while the next four in line will enter a 12-team play-off for another three berths next year.