Redknapp was only unveiled as the new boss just hours before the game, after the club sacked Juande Ramos following the club's worst ever start to a league campaign.
But the former West Ham and Portsmouth manager wasted no time stamping his authority at the club and saw strikes from Roman Pavlyuchenko and Darren Bent hand Tottenham a crucial win at White Hart Lane.
Redknapp has promised to bring the glory days back to White Hart Lane and will be pleased that his players showed all their fighting qualities to get their season back on track.
Redknapp received a superb welcome from the Tottenham fans before the game and his presence in the dug-out seemed to have an immediate effect on the players.
The home side could have broken the deadlock after just five minutes when Jamie O'Hara fired a 25-yard shot which deflected just over the bar.
David Bentley's corner then caused all kinds of problems for the Bolton defence and Andy O'Brien produced a great clearance to prevent Pavlyuchenko from nodding in at the far post.
Pavlyuchenko finally lived up to his reputation when he netted his first league for the club and fired Tottenham into the lead on 17 minutes,
Bentley's cross from the right picked out the Russian international who found himself completely unmarked in the box and he headed the ball past Jussi Jaaskelainen into the corner of the net to make it a dream start for Redknapp.
Bolton could have got back on level terms on 27 minutes following a major mix-up in the Tottenham defence. Kevin Davies reacted to the loose ball and drilled his shot inches past the post.
Gary Megson's side came even close to snatching an equaliser on 33 minutes following a mistake by Heurelho Gomes in the Tottenham goal.
Gomes failed to deal with free-kick from Matt Taylor. Johan Elmander picked up the loose ball and saw his shot cleared off the line by Ledley King.
Tottenham should have doubled their lead on 34 minutes when Jaaskelainen fumbled the ball, but Tom Huddlestone could only drag his shot over the bar.
Huddlestone came close again 60 seconds later when he made a clever turn on the edge of the box and drilled a powerful shot just wide.
The game swung massively in Tottenham's favour when Bolton were reduced to ten men after 56 minutes.
Gavin McCann was shown his second yellow card of the game following a late challenge on Huddlestone.
Ramos never got the best out of Luka Modric when he was in charge, but the Croatia international looked a completely different player and was one of the stars of the show.
Modric broke free into the Bolton box on 58 minutes and fired the ball straight at Jaaskelainen.
Redknapp will definitely strengthen his squad in January and could be considering a new keeper, after Gomes made two major blunders inside the space of four minutes which could have got Bolton back into the game.
Gomes first spilled the ball as he failed to deal with a long throw-in from Gretar Steinsson, but Kevin Nolan could only direct his shot over the bar.
The Brazilian keeper then failed to catch the ball again and Fabrice Muamba fired his effort just over the bar.
Gomes was let off the hook as Tottenham sealed the victory with the crucial second on 74 minutes.
Modric fired a superb shot on the volley which Jaaskelainen could only parry. Bent reacted the quickest to the ball but was brought down by the Bolton keeper and referee Andre Marriner immediately pointed to the penalty spot.
Bent kept his nerve to fire the spot-kick into the corner of the net to make it a happy first game in charge for Redknapp.