The midfielder, who signed a two-and-a-half year deal on Friday, finished off assists from Ben Gordon with either foot to continue Kilmarnock's impressive form.
Derek Riordan's magnificent long-range strike brought Hibs back into the game early in the second half.
But Edwin de Graaf wasted their best opportunity to level and their chances were further diminished when Liam Miller was sent off following some sustained indecision from referee Craig Thomson.
Much of the Rugby Park pitch was covered in a light sprinkling of snow after a fresh outbreak within two hours of kick-off, but Kilmarnock were still largely successful in playing the attractive brand of passing football that has now earned them five wins in seven SPL games.
The home side started well and almost benefited from several early through balls to Conor Sammon, who saw a diving header saved by Mark Brown in the opening stages.
Hibernian also had an early chance when a slip by James Fowler let in Miller, but the midfielder could not adjust his body properly and stabbed wide from six yards.
Killie took the lead in the ninth minute when Kelly finished off a wonderful flowing move.
Mehdi Taouil opened up Hibs by playing a reverse pass inside Michael Hart for Ben Gordon, who squared for Kelly to stroke the ball into the corner from 15 yards with his right foot.
Kilmarnock took a firm grip of possession and threatened again from Alexei Eremenko's corner, but neither Manuel Pascali or Craig Bryson could get a decisive touch.
Hibs were playing a fluid formation with Miller and David Wotherspoon supporting Riordan from midfield and they were getting enough men forward to trouble Killie on occasion.
The closest they came in the first half was when the ball broke for John Rankin 18 yards out, but Cammy Bell got down to block his 18-yard strike with his foot.
But the home side moved further ahead in the 43rd minute when Kelly produced another first-time finish inside the penalty box. Jamie Hamill's diagonal ball eventually fell for Gordon and his inside pass was swept home by Kelly from 10 yards with his left foot.
The second half started in uneventful fashion until Riordan produced a piece of magic 10 minutes in. The forward instantly took advantage of a few yards of room almost 25 yards out to unleash an unstoppable swerving strike into the top corner.
Hibs quickly brought on Colin Nish for Rankin and pushed more men forward. But they still struggled to cut open the Kilmarnock defence and the hosts began to find some rhythm previously missing in the second half to exploit gaps in the visiting defence.
Kelly saw a powerful long-range strike held by Brown, who then stretched to tip away Gordon's rising strike.
Hibs centre-back Sol Bamba went off with 15 minutes left with Jonathan Grounds moving inside and Daniel Galbraith coming on at left-back.
The visitors had the chance to level in the 78th minute when a brilliant piece of skill from Wotherspoon finally opened up the home defence.
He laid the ball to de Graaf in the inside right channel but the Dutchman took a heavy touch and blasted the ball into the side net to the disgust of three team-mates inside the box.
Hibernian's chances were soon undone when Miller was sent off after several minutes of controversy and confusion. The Irishman clipped the legs of Sammon as the striker ran into the diagonal edge of box following a slip by Grounds. Thomson gave a free-kick and maintained his decision following talks with assistant Brian McGarry as the home side claimed the offence had taken place inside the area.
Killie looked set to take the free-kick before another delay ensued as Thomson consulted fourth official Thomas Robertson, with the outcome being a straight red card.
The free-kick was taken short before eventually falling for Fowler, whose powerful volley was tipped over by Brown and Kelly almost claimed his hat-trick only for Hamill to over-hit his cutback.