Valencia took the lead in the 17th minute when striker David Villa steered a low shot under keeper Victor Valdes after defender Miguel swept a perfect pass behind the Barca back four.
But the home side kept their composure and equalised at the start of the second half, substitute Andres Iniesta clipping home after Ronaldinho and Samuel Eto'o combined to prise open the Valencia defence.
Sevilla, the only other side with a perfect record, lost for the first time in any competition since last April when they went down 2-1 at Atletico Madrid.
Brazilian midfielder Renato gave Sevilla a deserved lead late in the first half, but the match was turned on its head when they had centre-backs Julien Escude and Javi Navarro sent off in the second half.
Atletico laid siege to Sevilla's area and Maxi Rodriguez struck twice in the last five minutes to give the home side a dramatic win, his first a thundering 20-metre drive and his second a close-range effort after great work by Fernando Torres.
The weekend's results left Barca top on goal difference ahead of arch-rivals Real Madrid, who ground out a 1-0 win at Real Betis on Saturday, and Valencia.
Sevilla and Atletico follow a point behind the leading trio with nine points from four games.
FIRST GOAL
Last season's Champions League semi-finalists Villarreal found the net for the first time this season when they came from behind to clinch a 3-2 win at home to Real Zaragoza.
Racing Santander gained their first points of the season in a 2-2 draw at Gimnastic, both goals coming from giant Serbia striker Nikola Zigic.
Levante inflicted a first defeat of the season on Deportivo Coruna, former Juventus midfielder Olivier Kapo earning his side a 2-0 win with classy goals in either half.
Valencia had not lost at the Nou Camp since 2001 when Rivaldo scored a hat-trick, including a dramatic last-gasp overhead kick to give Barca a 3-2 win.
They made life difficult for the Catalans again as Villa put the visitors in front when he got ahead of Gianluca Zambrotta to send a low shot under Valdes after Miguel had sent a wonderful pass skidding behind the defence in the 17th minute.
It was the Valencia striker's fourth goal against Barcelona in three matches but despite the setback the home side were always in the game.
They equalised when Iniesta scored within three minutes of coming on at the start of the second half after Samuel Eto'o headed a Ronaldinho cross into his path as he entered the area.
Late substitute Javier Saviola, making a rare appearance for Barca, missed a late chance to snatch victory.
