Two first-half goals were the difference in the end, despite Gretna's last-minute consolation.
Perhaps Gretna's chance of at least a point disappeared in the 58th minute when Colin McMenamin failed to hit the target with a penalty, but the winning margin could have been greater as Killie twice hit the woodwork in the second half.
The visitors grabbed a fourth minute lead when Colin Nish sent Rhian Dodds scurrying down the line and his cross was met at the edge of the box by Willie Gibson and he thumped a great left-foot shot into the net.
Gibson and Nish both came close, as the visitors piled on the pressure looking to increase their lead.
Kilmarnock keeper, Alan Coombe, made his first save midway through the first half, pushing away a Craig Barr cross.
After 36 minutes, Killie doubled their lead with Ryan Jarvis hitting the net. Grant Murrary's deep cross was headed back across goal by Nish and Jarvis, on loan from Norwich, thumped home from 12 yards.
Gretna were given a lifeline two minutes later when Fabian Yantorno was upended in the box by Murray. McMenamin stepped up to take the kick, but looked on in despair as his effort hit the underside of the bar before being cleared.
Just before half-time Nish saw his effort booted off the line by Chris Innes after a dreadful mix-up in the home defence.
Half-time substitute Erik Paartalu saw his header hit the top of the bar as Gretna tried to grab an equaliser in the second half.
As Kilmarnock once again got a foothold in the game, Innes tried to clear his lines and almost knocked a Gibson cross into his own net, being saved by the post.
Kilmarnock substitute, David Fernandez, with his first touch sent Nish rushing through only to see his terrific lob, which beat Fleming, crash off the bar before being cleared.
Four minutes from time the visitors once again got beyond the home defence, but this time keeper Greg Fleming reacted well and was able to push away a good effort from Dodds from close range.
Gretna's goal, in injury time from Gavin Skelton, proved to be no more than a consolation.