The Turkish visitors went ahead in the 14th minute when Roberto Hilbert struck into the far corner having latched on to Ricardo Quaresma's pass, but their lead lasted only a minute, goalkeeper Rustu Recber unable to claim Dean Whitehead's corner and Peter Crouch on hand to bundle the ball over the line.
The two teams, roared on by their equally-vociferous sets of fans, played out an entertaining contest from there, with both hitting the woodwork in the second half.
Walters then settled things in the 78th minute, hammering his spot-kick past Rustu after Crouch had been brought down by Tomas Sivok.
Stoke boss Tony Pulis made seven changes to his first XI, with Crouch, Matthew Etherington, Rory Delap and skipper Ryan Shawcross the only survivors from the team that started Saturday's 1-1 Barclays Premier League draw with Manchester United.
Besiktas' line-up featured some familiar names, including former Everton midfielder Manuel Fernandes and one-time Chelsea man Quaresma, who fired in the first shot on goal in the second minute, an ambitious effort from outside the box that went harmlessly wide.
At the other end, Rustu flapped at a trademark Delap long throw into the area, although referee Antony Gautier judged the stopper had been blocked by Shawcross.
Whitehead delivered a corner into the danger zone which Robert Huth headed wide and Quaresma tried his luck from a similar distance as before, again shooting off-target.
The Portuguese player's accuracy was spot-on three minutes later, though, his through-ball deceiving Huth and allowing Hilbert to finish past Thomas Sorensen.
The Potters' response was almost instantaneous, as Rustu failed to get to Whitehead's corner under the attentions of Shawcross and Crouch tucked the loose ball home.
Etherington then lofted a pass forward which Cameron Jerome headed on to the roof of the net, before sending in a corner which Crouch nodded the wrong side of the post, Rustu impeded once more and earning a free-kick.
Crouch got on the end of another Delap throw but could not convert, before Sorensen punched away Fernandes' effort and saw one from Quaresma sail wide.
Huth then went close with a drilled attempt into the side-netting and just before the interval, Etherington's free-kick flashed across the Besiktas six-yard box but no-one was able to prod it in.
Only a few minutes after the restart Etherington had to come off for Jermaine Pennant and Stoke survived Besiktas appeals for a penalty when Gautier ruled Matthew Upson had not handled from a corner.
Rustu got behind a well-executed volley from Whitehead to catch the ball, and the goalkeeper then got down to deflect a shot from Walters - who had come on for Jerome - against the frame of the goal.
Shawcross headed Pennant's free-kick too high and Walters' drive brought another save out of Rustu.
The visitors then almost regained their advantage in farcical style as Quaresma's shot looped off Huth and hit the top of the post.
The game seemed anyone's to win and Delap lifted the ball over the bar from a good position before substitute Glenn Whelan struck wide.
With just over 10 minutes remaining, though, Stoke were handed their chance as Crouch went down in the box under Sivok's challenge and Gautier pointed to the spot.
Sivok was shown a yellow card and Walters rifled the penalty in.
Sorensen then denied Edu with a great save to ensure the Potters made it four points from their opening two group games.