The midfielder's shot from the edge of the penalty area squirmed away from the despairing dive of Orient goalkeeper Jamie Jones and rolled into the net.
Orient were only denied an upset in the original tie 10 days ago by a last-minute Nick Proschwitz equaliser.
And Hull left it even later to finally see off their League One opposition in the replay and secure an all-Yorkshire showdown with Championship rivals Barnsley.
Proschwitz had earlier given them the lead with a stunning strike, only for a freak Dean Cox goal to force extra time.
There had been little sign of what was to come as Hull, and Proschwitz, laboured throughout the majority of the first half.
He had a weak header saved by Jones and blazed a free-kick high over the crossbar.
But Proschwitz found his range in the 41st minute with an outstanding goal, flicking up Liam Rosenior's cross with his first touch before swivelling and rifling a 20-yard volley past Jones with his second.
It was harsh on Orient, who had dominated the opening stages with their diminutive winger Dean Cox causing no end of problems.
Cox looked to have created an opening goal in the 21st minute after another jinking run when his shot was deflected onto a post. The ball fell to the feet of David Mooney, who crashed it past Hull goalkeeper Eldin Jakupovic, but the striker's celebrations were cut short by an offside flag.
Os left-back Gary Sawyer then whipped in a cross which was met by the unmarked Jimmy Smith, only for the former Chelsea youngster to plant his header over the crossbar.
It was a poor miss, and looked all the more costly when Proschwitz produced his moment of magic at the other end.
In the second half Jay Simpson twice should have made the game safe, shooting too close to Jones with his first effort and scuffing a second wide.
Orient had another goal ruled out for offside when Lee Cook slid the ball home, but they levelled in bizarre fashion when Cox's cross flew over the head of Jakupovic and straight into the net with three minutes remaining.
However, Hull had the last word in extra-time when Orient could only clear Proschwitz's cross to the edge of the area and Cairney fired it back past Jones.