Robbie Keane netted a priceless away goal but Spurs still face a tough task to reach the Uefa Cup semi-finals after Sevilla hit back to win this first leg.
Keane took Dimitar Berbatov's pass and slotted home after just 68 seconds.
Ex-Spurs striker Fredi Kanoute pulled the holders level from the penalty spot after Paul Robinson was harshly ruled to have tripped Claro Adriano Correia.
And Alexander Kerzhakov headed the winner on 35 minutes as ugly crowd disturbances marred an excellent match.
Sevilla, bidding to become only the second side to defend the Uefa Cup after Real Madrid's back-to-back wins in 1995 and '96, made a host of changes to the side that started against Osasuna at the weekend.
But they were stung in only the second minute as Tottenham grabbed a precious opener.
Berbatov threaded a clever ball through for Keane and the Irishman, despite seeing his first effort blocked by Valencia keeper Andres Palop, clipped home the rebound to send the 4,000 away fans into ecstasy.
Aaron Lennon's clever reverse ball almost put Keane through again in the seventh minute but it was well collected by Palop.
But Valencia were thrown a lifeline as Robinson was adjudged to have dragged down Correia when he appeared to have cleanly clawed the ball away from the Sevilla's player feet.
Referee Alain Hamer, from Luxembourg, immediately pointed to the spot despite furious protests from the Spurs players.
Kanoute, the French-born Mali striker, coolly slotted the spot-kick to Robinson's left for his 24th goal of the season.
That lifted Sevilla, who have lost just once at home in La Liga this season while claiming the scalps of Valencia, Barcelona and Real Madrid in the process.
And the pressure finally told after 35 minutes when Russian hit-man Kerzhakov headed home after Michael Dawson hesitated after Julien Escude's cross from the right.
Six minutes later, Kerzhakov then cut in from the left and fired a curling strike which flashed wide of the Tottenham goal.
Tottenham seemed distracted by the shocking crowd violence behind their goal and needed the half-time interval to take stock.
They came out more composed after the break and retook the initiative with Keane rasping a fierce drive wide from the left side of the Sevilla penalty area.
Their over-enthusiasm prompted yellow cards for Lee Young-pyo, Didier Zokora and Teemu Tainio as they tried to match Sevilla's aggressive tactics.
Kanoute should have made it 3-1 when he headed wide from 12 yards.
But Zokora threatened to break his duck for the Londoners when his powerful surge on 75 minutes ended with a tame shot that drifted wide.
Substitute Steed Malbranque snatched at a good opportunity when put through by Keane on 85 minutes as Tottenham pressed for an equaliser.
But they were unable to find the goal and suffered their first defeat in the Uefa Cup this season.
However, given the quality of the opposition, Spurs will be relatively satisfied with a 2-1 deficit and hopeful of pulling the tie around at White Hart Lane in a week's time.
Sevilla: Palop, Javi Navarro, David (Dragutinovic 68), Daniel, Escude, Renato (Marti 60), Poulsen, Adriano Correia, Kerzhakov, Kanoute, Jesus Navas.
Subs Not Used: Cobeno, Duda, Chevanton, Hinkel, Maresca.
Goals: Kanoute 19 pen, Kerzhakov 36.
Tottenham: Robinson, Stalteri, Chimbonda, Dawson, Young-Pyo Lee, Lennon (Malbranque 80), Zokora, Jenas, Tainio (Ghaly 84), Keane, Berbatov.
Subs Not Used: Cerny, Mido, Defoe, Taarabt, Ifil.
Booked: Robinson, Tainio, Young-Pyo Lee, Zokora.
Goals: Keane 2.
Ref: Alain Hamer (Luxembourg).