Celtic were awarded the first penalty when Shaun Maloney dribbled into the box where he was tripped by Garry Hay.
Maloney stepped up to take the spot-kick and sent Alan Combe the wrong way, but missed the target wide to the left.
Georgios Samaras then volleyed tamely into Combe's arms after great set-up work by Shunsuke Nakamura, but Celtic did take the lead in the 26th minute and it was Maloney who achieved retribution with an opportunist strike.
The ball fell loose at the edge of the Killie box and the little striker put his penalty miss behind him by sending the ball high past Combe and into the top corner.
Samaras passed up a great chance to put Celtic clear four minutes before the interval when he ran clear from a suspiciously offside position.
He reached the six-yard box but, like Maloney's penalty, he sent his shot sliding past the far upright.
Killie keeper Combe did his international hopes no harm with a stunning block from a point blank Jan Vennegoor of Hesselink header five minutes into the second half to keep his team in it.
But Celtic, who were inspired by Scott Brown, were in total command and Samaras made up for his first half sloppiness in front of goal with a stunning individual strike in the 56th minute.
He simply ran away from Fraser Wright on the right touchline and made straight for Combe, who was helpless as the Greek passed the ball into the corner of the net.
Samaras linked with Vennegoor of Hesselink again in the 64th minute, but this time his shot clipped the far post and bounced clear.
Kilmarnock almost set up a grandstand finish as substitute Donovan Simmonds profited from a Samaras slip, but his low cross just evaded Conor Sammon.
Celtic made it three nine minutes from time when they were awarded their second penalty of the day.
Nakamura went down under a challenge from Craig Bryson and the Killie players were livid when the referee pointed to the spot.
Combe guesses right, but Samaras' shot had enough power to reach the net.
Just when the game looked dead, a goalmouth scramble ensued and Gary Caldwell had to handle to prevent Killie scoring and was duly sent off leaving Mehdi Taouil to score beneath the diving Artur Boruc.