Chris Sutton netted a hat-trick, goals also came from John Hartson and substitute Shaun Maloney.
Martin O'Neill made three changes to last week's side - Liam Miller was played on the right in place of rested Didier Agathe, Jackie McNamara won back his place from Joos Valgaeren and Mickey Gray took Alan Thompson's place on the left hand side.
Celtic's first goal came from a penalty in 19 minutes. Stillian Petrov won the penalty, TV replays showed that Petrov certainly made the most of the challenge but I'm not complaining.
Chris Sutton stuck the ball in the corner of the net to put the league leaders 1-0 up.
Liam Miller impressed once again, and almost grabbed a goal when a wonderful return pass from Larsson landed in his path. Miller chipped the ball beautifully over the goalkeeper and the Celtic fans were almost celebrating, but a goal line clearance from Greer prevented a second goal.
Killie never looked like scoring, they had one attempt at goal in the first half which fizzed by Magnus Hedman's post.
Henrik Larsson made a terrific run moments before the half time whistle, and it looked like the run would end up in a superb goal. However, his shot bounced unluckilly back off the post.
Celtic were playing some good football, but lacking in the last third of the park. But on 69 minutes, The Bhoys decided they were playing too much like Rangers and stepped up a gear for the second goal.
From a free kick, Henrik Larsson passed the ball out wide to Mickey Gray, who's neat cross into the box was powerfully headed home by John Hartson. The Welshman looked delighted with his goal as he headed off to celebrate with the Celtic fans.
Seven minutes later it was game over. Hartson released a poor ball to Larsson the the right, and his cross was smashed home by Chris Sutton. "What a f*cking ball!" said the Englishman when he celebrated with Larsson.Quite right big man, quite right.
Martin O'Neill replaced Neil Lennon, John Hartson and Michael Gray with Shaun Maloney, Ross Wallace and momo Sylla with 10 minutes to go, and Maloney got Celtic's fourth with his first touches of the ball.
Ross Wallace crossed a great ball to Maloney who was in plenty of space, he had the time to pick his spot to send the Killie fans home, probably too late to catch the bus for Ibrox but never mind lads, the game is on the radio.
Chris Sutton grabbed his third from the penalty spot with only minutes left. Larsson was brought down by that hippy looking guy and Big Chris done the business again.
I'm delighted to get the win with Anderlecht coming up midweek, and also making all those huns-in-disguise Kilmarnock fans sick!
The Bhoys remain top of the SPL.
Celtic:
Hedman - 7
McNamara - 7
Varga - 8
Balde - 8
Gray - 7 (Wallace - 7)
Lennon - 7 (Sylla - 4)
Sutton - 9
Petrov - 8
Miller - 8
Hartson - 7 (Maloney - 8)
Larsson - 9
Celtic-Mad Man of the Match: Chris Sutton