Gary Warren scored a brace either side of Billy McKay's deflected effort with Hearts twice levelling the game through Jason Holt and Andy Webster.
Caley Thistle opened the scoring on 15 minutes when Warren planted his header into the net after connecting with an Aaron Doran free-kick.
Owain Tudur Jones smashed another free-kick through the Hearts defensive wall and narrowly wide of the target with the keeper well beaten.
And McKay was denied by the flag when he thought he had sprung the offside trap to stick the ball past Jamie MacDonald later in the half.
Hearts hit back when Arvydas Novikovas and Darren Barr combined to set up Holt (55) on the edge of the box and he stole a yard on Warren before crashing his shot past Ryan Esson.
Parity lasted just six minutes before Tudur Jones nodded a David Raven free-kick to the back post and McKay squeezed his header between Callum Tapping and the goal.
Hearts gain hit back after winning a disputed corner from which Michael Ngoo's header was cleared off the line by Nick Ross, but the danger was not cleared and Webster (74) fired a volley home from the edge of the box.
Warren settled the issue on 77 minutes when he timed his run to perfection to meet a Graeme Shinnie corner and power his header past MacDonald.