The opening goal of a largely one-way contest came in the 37th minute as Roberto Soldado calmly converted from the penalty spot after Ryan Shawcross blocked Emmanuel Adebayor's acrobatic shot with his arms raised.
Stoke may have some complaints over referee Kevin Friend's decision given the proximity of Shawcross to the Spurs striker, but having both arms high over his head as he went into challenge after Soldado's fine pass was always taking a major risk.
Adebayor and Soldado had earlier missed decent chances for the home side, while Stoke will feel aggrieved they did not get the decision from Friend when Zeki Fryers tangled with Jonathan Walters on the edge of the area.
Mousa Dembele doubled Spurs' lead in the 65th minute with an impressive strike from long range as he worked a yard of space to get away from Steven Nzonzi outside the area before drilling a fine low shot into Thomas Sorensen's bottom corner.
And the contest was over four minutes later as the returning Aaron Lennon scored his first goal of the season, volleying the ball back across Sorensen in fine style after being found by Soldado's pass. The win moves Spurs into seventh in the table, just three points off the top four.
Tottenham were flat and wasteful in Sherwood's first full game in charge on Boxing Day, but on Sunday they were far better and managed to keep a clean sheet in the league for the first time since November 3.
Dembele and the returning Paulinho bossed the midfield while Lennon's performance on the right flank gave Tottenham the cutting edge they lacked against the Baggies.
Stoke never looked like threatening the Spurs goal, although manager Mark Hughes may be aggrieved that Michael Dawson was not penalised for his challenge on Oussama Assaidi.
Mark Hughes was on his feet complaining after four minutes. Walters was barged over by Fryers after latching onto a long ball over the top, but referee Friend waved play on.
Dawson buried a volley deep into the away fans and Sherwood was annoyed at his team for not creating enough chances.
Tottenham's first real opening came when Lennon got behind the Stoke defence following a pass from Kyle Naughton, but neither Christian Eriksen nor Adebayor could finish.
Spurs were back on the attack through Lennon, who turned Erik Pieters inside out - but Shawcross diverted the ball away from the three Spurs players who were lurking in the box.
Sherwood finally had a smile on his face after 36 minutes when Soldado gave Spurs the lead.
Friend pointed to the spot when Adebayor's acrobatic volley struck Shawcross' outstretched arm and Soldado converted to maintain his flawless record from 12 yards.
Tottenham continued to dominate after the break as Dembele held onto the ball majestically in midfield. He got the goal his performance deserved just after the hour. The midfielder looked to have run out of options when he checked inside from the right, but after dropping the shoulder he escaped Nzonzi and drove a left-foot strike into the bottom corner past Sorensen.
A third goal came soon after as Soldado's cross found its way to Lennon at the back post via Adebayor's boot and the England winger despatched a dipping volley past Sorensen.
Lennon received a standing ovation when he was replaced by Erik Lamela with 15 minutes left and the Argentinian would have had his first Premier League goal soon after had Geoff Cameron not put in a fine block after a lay-off from Adebayor.
Crouch had half a chance to pull a goal back for Stoke, but he wasted it and Tottenham achieved their first league win at home since October 27.