Second-half goals from Charlie Adam and Ryan Shawcross were enough to give them the three points after they had trailed Ian Holloway's side 1-0 at the break.
Marouane Chamakh had given the visitors the lead just past the half hour after Stoke were undone by a long punt upfield. Shawcross let the ball bounce and was then outmuscled all too easily by the former Arsenal striker, who proceeded to wrong-foot Robert Huth and fire low past Asmir Begovic in the Stoke goal.
That's how it stayed until the break but the hosts were much improved in the second period and had already come close before Adam equalised after Jon Walters kept his cool amongst the confusion in the Palace area to set up the Scotsman.
The visitors were stunned and things went from bad to worse for them just minutes later. Chamakh's clearing header was poor and, as the ball came back, his attempt to make amends was even worse and allowed Shawcross to swivel and fire Stoke into the lead.
That was how it remained and Hughes will be relieved to see his Stoke reign up and running, whilst Palace and Holloway remain pointless after two games.
Both Stoke and Palace were looking to bounce back from 1-0 defeats on the opening weekend of the season, and it was the home side who started the contest most brightly.
Adam drilled a low shot from outside the box into the arms of Julian Speroni in the sixth minute and the Potters continued to pressurise, winning three corners in quick succession but not being able to make anything of it.
Dwight Gayle tried his luck at the other end in the 16th minute with a strike that Begovic got down to save, and Palace fans then appealed for a penalty when Joel Ward went down in the area under the attentions of Matthew Etherington, but referee Andre Marriner judged there had been no foul committed.
Peter Crouch passed up an opportunity to put Stoke ahead in the 21st minute, nodding Etherington's cross over the bar from inside the six-yard box.
Palace had steadily been growing into the contest and, just after the half-hour mark, they snatched the lead as Chamakh made the most of some poor Stoke defending.
Alongside Shawcross, Chamakh chased a long ball which had been lofted forward by Damien Delaney, shrugged off the Potters defender with relative ease, cut inside - fooling Robert Huth - and slammed a shot past Begovic.
The hosts almost found an immediate reply as Crouch rose to get his head to Adam's delivery and sent the ball against the bar.
Palace were soon back on the attack, though, with Dean Moxey flashing an effort across the face of goal and narrowly wide.
Jose Campana then looped a free-kick over the bar as the visitors finished the first half strongly.
Stoke began the second period looking intent on getting themselves back in the game and, within two minutes of the restart another good chance was missed by Crouch, with the striker completely miscuing an attempted header from a corner.
The equaliser arrived on 58 minutes as Walters received the ball from Crouch's header and laid it to Adam, who placed it past Speroni into the net.
Stoke's momentum then swiftly yielded another goal as Huth and Shawcross made amends for their earlier sloppiness. Good perseverance in the box from the former saw the ball break for Shawcross to smash it home.
Jason Puncheon went close to scoring a quick leveller, bursting into the box and unleashing a strike which Begovic slowed with a finger-tip at full stretch before smothering.
Stoke then nearly added to their tally as Nzonzi lashed the ball against the post.
Palace remained full of belief and, after substitute Kevin Phillips had shot wide, Gayle was off-target with an ambitious volleyed attempt.