Andy Butler saw red for the Saddlers in just the 18th minute and David Mooney duly put the League One leaders ahead at the break.
But Craig Westcarr's second-half leveller earned Walsall a deserved point at Brisbane Road in front of 5,429 - Orient's biggest home attendance of the season - before Romain Vincelot was then dismissed for the hosts deep into injury time.
The visitors were reduced to 10 men when Butler was shown a straight red by referee Graham Scott after a lunging tackle on Orient midfielder Vincelot although he appeared to win the ball.
Mooney, who had hopelessly missed the target when put through by Dean Cox, took just two minutes to rectify his error after a blunder by goalkeeper Richard O'Donnell.
Challenged by Kevin Lisbie, the Walsall stopper spilled a cross from Lloyd James and Mooney slammed the ball into the net from 15 yards for his ninth league goal of the campaign
However, the home side were unable to regain their tempo after the break and were punished for some sloppy play when a cross from the left was nodded back across goal by Troy Hewitt for Westcarr to score from close range.
O'Donnell was to become the visitors' saviour, though, with two stunning saves in the second period. First he kept out Lisbie's header from point-blank range and then, with two minutes of normal time remaining, tipped a powerful effort from Matty Baudry on to the crossbar.
Vincelot took an early bath when he was dismissed in added time for a second bookable offence.