Isaac Price netted twice for West Bromwich Albion at St. James' Park, first giving them a 19th-minute lead then threatening to force extra time after Bazoumana Touré had netted on his debut and Barnes had come off the bench to nudge Newcastle ahead.
But Barnes - who spent part of the 2018/19 campaign on loan with the Baggies - had other ideas, grabbing his second of the night in front of a 51,405 crowd, including new signing Nico González.
The Spaniard was announced and unveiled just before kick-off and the former Manchester City midfielder must have enjoyed a match which, like Sunday's 2-2 Premier League draw with Liverpool, was high on drama throughout.
Joe Willock came close for the Magpies in the seventh minute. The midfielder - who scored against Liverpool three days earlier - almost made it two in two games as he made space for a shot but fired wide.
Then Lewis Hall's half-volley was fielded by Matt Ingram, the visiting goalkeeper.
But at the other end, Jaouen - like Touré, making his Magpies bow - was unable to keep out Price's audacious free kick.
New signing Nico González was announced and unveiled to the capacity crowd just before kick-off, creating a raucous atmosphere, but the home fans were silenced when the Championship side went ahead.
Jimmy-Jay Morgan then dragged an effort wide for Albion just before the half-hour mark, but United pushed for a leveller before the interval.
Touré had an opportunity to do just that, but his shot lacked the power to trouble Ingram.
But the Ivorian did equalise in the 38th minute, converting from close range following a searching centre from Dedić.
Barnes entered the fray at half time - replacing the black and white goalscorer - and wasted no time in making an impact himself.
His initial shot was blocked, but he reacted first to force home.
The England winger tried his luck again in the 69th minute, but this time his strike was straight at Ingram.
The away side fought back when Hall was penalised for handball and Price sent Jaouen the wrong way from the spot.
Hall suffered more misfortune moments later when his powerful shot cannoned back off a post. Then Wissa was off target at full stretch as extra time loomed.
But Barnes made it 3-2 with a smart finish from another Dedíc cross to send United into the next round of a competition they famously won in 2025 - although only after a flying Jaouen save to push away Jayson Molumby's late free-kick.
Newcastle United: Ewen Jaouen, Lewis Hall, Sven Botman, Malick Thiaw (c), Sean Steur (Lewis Miley 65), Bazoumana Touré (Harvey Barnes 46), Jacob Murphy (Anthony Elanga 65), Nick Woltemade, Joe Willock (Yoane Wissa 65), Amar Dedić, Jacob Ramsey
Substitutes: Lucáš Horncíček, Fabian Schär, Aladji Bamba, Leo Shahar, Sean Neave
