The two parties are now discussing a compensation package after it became clear in a meeting on Wednesday with Redknapp and Paul Stretford, the agent appointed to negotiate a new contract for the 65-year-old, who had a year to run on his existing deal.
REDKNAPP'S RECORD AT SPURS PLAYED 198 WON 98 DRAWN 50 LOST 50 WIN PERCENTAGE 49.5%
The boss' departure is likely to be explained as a mutual agreement between both parties but, ultimately, the decision was made by Levy after the former Portsmouth boss made it clear he felt his time was up but refused to resign.
"This is not a decision the Board and I have taken lightly," Levy stated on the club's official website.
"Harry arrived at the club at a time when his experience and approach was exactly what was needed. This decision in no way detracts from the excellent work Harry has done during his time with the club and I should like to thank him for his achievements and contribution.
"Harry will always be welcome at the Lane."
Redknapp added: "I have thoroughly enjoyed my time at Spurs and am proud of my achievements. I have had a fantastic four years with the club - at times the football has been breathtaking.
"I am sad to be leaving but wish to thank the players, staff and fans for their terrific support during my time there."
Levy had made it clear that Redknapp would not be offered the three or four-year contract that he wanted after holding the manager responsible for Spurs' failure to achieve a place in next season's Champions League having thrown away a 10-point lead over rivals Arsenal.
The hierarchy at White Hart Lane felt that Redknapp had been distracted by speculation linking him with the England job and concerns were raised about his match preparation, training and tactics.
Redknapp, who was appointed Spurs manager when the Londoners were bottom of the table in October 2008, took the club to two fourth-placed finishes in three full seasons but had a prickly relationship with Levy throughout his time at White Hart Lane.
Wigan manager Roberto Martinez and Everton boss David Moyes are expected to be the leading candidates to replace Redknapp. Brendan Rodgers, the new Liverpool manager, was previously the club's first choice candidate before he was appointed to the Anfield hotseat.
Redknapp was forced to deny rumours on Tuesday that he had quit Spurs but the decision was made for him by Levy, who is thought to have been particularly angered by Redknapp's public maneuvering for a new deal.
He had suggested that players would be unsettled if he was not offered a longer deal, having previously claimed that the squad would not be affected by speculation linking him with the England position.