35 mins
Steven Pressley stumbled as Steven Naismith set up Invincibile and the Australian fired in the opener.
Mirsad Beslija was next to lose his footing in the lead up to the second as Wales' effort was deflected home.
Naismith struck the crossbar before Hearts pressed forward after the break but failed to make their pressure tell in terms of goals.
Hearts head coach Valdas Ivanauskas had made four changes as he continued his squad rotation policy.
Robbie Neilson returned at right-back, while there were also recalls for Mirsad, Roman Bednar and fit-again Edgaras Jankauskas.
Andrius Velicka, Jamie Mole and Marius Zaliukas dropped to the bench while Saul Mikoliunas was suspended.
Fit-again Gordon Greer replaced Simon Ford in Kilmarnock's defence, which was quickly under pressure.
Deividas
Cesnauskis' clever flick set Jankauskas clear and
only a deflection off a Kilmarnock defender stopped
the Lithuanian putting the Jambos ahead and Beslija
also had an effort deflected wide.
Killie rode out the initial storm and James Fowler shot over the Hearts bar from the edge of the box when he should have done better.
And the visitors took the lead when Danny Invincibile (right) finished beautifully after being fed by Naismith, who had burst forward from midfield.
His path made easier by a slip on the greasy surface from Hearts skipper Pressley and a slip by Beslija led to Kilmarnock's second goal.
Former
Hearts striker Gary Wales effort was
deflected off Christophe Berra past a flat-footed
Craig Gordon.
Paul Hartley tried to haul the home side back into the game, but goalkeeper Graeme Smith beat out his free-kick and dived on the loose ball with several attackers waiting to pounce.
Killie almost made it 3-0 when Wales nodded Garry Hay's free-kick back across goal and Naismith headed against the crossbar.
Hartley forced Smith into another fine save after the break following a good run by the Scotland midfielder.
Beslija set up Bednar, who sent a drive just wide.
But Killie forward David Fernandez flicked on for Peter Leven, who ought to have done better than fire against Gordon's legs from eight yards.
Sandy's Match Pic's are HERE
