Leeds fell behind to a converted try by Perpignan wing Samueli Dawai-Naulu but hit back to lead 8-7 as Gordon Ross crossed for a try and added a penalty.
They held their advantage until the final quarter when Dawai-Naulu scored his second try for the hosts.
The Tykes pressed hard but could not avoid slipping to a second pool defeat.
They must now win their remaining matches against Calvisano (away) and Cardiff Blues (home) with bonus points to retain their slim hopes of topping the group.
Leeds director of rugby Phil Davies:
We're as pleased as you could be after losing a game of such importance. We defended really well throughout and showed a high level of commitment. The guys did really well to get back on their feet after conceding early.
It was intimidating, but the atmosphere was great and I'm delighted that some of the younger members of our squad got a chance to experience it.
Perpignan: Edmonds; Bomati, Manas, Grandclaude, Cermeno; N Laharrague, Durand; Freshwater, Konieck, Mas; Gaston, Hines; Le Corvec, Goutta, Robertson.
Replacements: Tincu, Debaty, Porcu, Tonita, Dupuy, Vaki, Dawai-Naulu.
Leeds: Doherty; Snyman, Vickerman, Jones, Biggs; Ross, Marshall; Cusack, Bulloch, Kerr; Murphy (capt), Morgan; Dunbar, Thomas, Reid.
Replacements: Gerber, Rawlinson, Palmer, Crane, Care, De Marigny, Bell.