Adebayo Akinfenwa's seventh goal of the season was enough to extend the Gills winning run to five games.
The result saw them rise another two places up the League Two table into seventh, the final play-off spot.
It certainly wasn't as pretty or convincing as the impressive victory over Port Vale on Tuesday but sometimes you just accept the points however they come.
Stevenage proved to be a no-nonsense side, they battled hard for every ball and were a tough nut to crack.
Following the midweek win, boss Hessenthaler was able to name an unchanged squad, Joe Martin was able to play with his forehead bandaged following the cut he received in that game.
The first real moment of note, as both sides looked to gain the upper hand early on, was a fourth minute booking for Chris Beardsley following a late challenge on Barry Fuller.
Stevenage looked to unsettle the Gills with some heavy-handed tactics, on top of the early booking, Scott Laird was spoken to by referee Iain Williamson for a barge from behind on Danny Spiller while Adebayo Akinfenwa seemed to be targeted by any defender in his vicinity.
There were no prisoners being taken by either side and despite handing it out, the visitors were quick to moan when some hard challenges were put in on them. Although the referee did seem rather lenient, both ways.
The first real chance of the game came in the 16th minute. Cody McDonald played a deep one-two with Akinfenwa before using his pace to go past Boro's last line of defence but as keeper Chris Day advanced to narrow the angle, the strikers shot bounced off him and went out for a throw.
Stevenage's best chance came in the 28th minute when a Byron Harrison header forced Alan Julian to make a flying one-handed save down to his left-hand side.
After a spell where Stevenage stifled the Gills, it was Fuller who made a great break forward, only to be denied on the edge of the area by Mark Roberts outstretched foot.
The Gills took the lead in the 38th minute with a well-taken goal. McDonald fed Akinfenwa who looked to return it to the marauding loan striker. However when that route was blocked he laid the ball out to Spiller on the right. Akinfenwa didn't just stand and watch though, getting into the box to meet Spillers great curling cross with a diving header that gave Day no chance.
In the two minutes of time added-on, Luke Foster became the second visiting player to be yellow-carded for a blatant body-check on McDonald as he looked to break through.
Then Akinfenwa had another shot saved by Day at his near post following a good ball from Curtis Weston.
The Gills started the second-half brightly with Fuller, on the right, and Martin, down the left, causing Graham Westley's side problems - however the only real effort, from Kevin Maher, flew high into the Rainham End.
Beardsley, already on a booking and a lecture moments earlier following an incident with Matt Lawrence, was perhaps lucky to stay on the pitch when he left a foot dangling as he challenged for a ball with Julian, referee Williamson showed leniency once again with just a calm-down motion to the striker.
Although Boro introduced two substitutes in quick succession and had a lot of the ball, especially when the Gills began to look a bit nervy at the back, they were struggling to create any clear-cut openings.
Andy Barcham came on for John Nutter in the 67th minute, a switch which saw Martin drop into his preferred left-back role.
The Gills should have gone two-up in the 73rd minute, McDonald collected a through ball, rounded Day and looked odds-on to roll the ball into an empty net but somehow the lunging figure of Foster managed to block.
Mark Bentley and Stefan Payne were then introduced, for Akinfenwa and Maher who had both worked tirelessly for the cause.
The luck certainly didn't seem to be on McDonald's side. From the resultant Spiller corner he should have done better than head wide at the far post when unmarked, then in a short space of time, he was twice set up by Weston. Day was in the right place to block his first effort and the second he pulled into the near post side-netting from yet another great position.
Yet another chance fell his way in the 81st minute when a Fuller clearance helped put him in down the right, but he once again shot straight at Day.
As the clock ran down, Stevenage began to bombard the Gillingham defence putting them under enormous pressure and they survived a couple of major let-offs. A fierce shot from Rob Sinclair saw Julian parry brilliantly but the ball fell perfectly for Ben May, his first-time effort was bravely blocked by Martin who flung himself in front of the ball at close range. From the resultant corner, Julian was again in the right-place to make a double block.
Time after time the ball was lumped into the Gills area but Lawrence and Josh Gowling led by example and they, or anybody else, would put their bodies on the line to ensure the visitors didn't get a thing.
There was also a fair bit of attempted time-wasting and eventually Spiller was shown a yellow card for stealing a second or two too many at a free-kick but the final whistle eventually blew and not only was the fifth straight win secured but, almost as importantly defensively, a third clean sheet was recorded.
Gillingham: Julian, Fuller, Gowling, Lawrence, Nutter (Barcham 67), Spiller, Weston, Maher (Bentley 76), Martin, McDonald, Akinfenwa (S Payne 76). Unused subs: King, Rooney, Jackman, Cronin,
Stevenage: Day, Wilson, Laird, Foster, Long (Sinclair 60), Griffin, Roberts, Beardsley, Mousinho, O'Shea (May 73), Harrison (Odubade 62). Unused subs: Bayes, Byrom, Winn, Maamria
Assistant: Carl Berry & Philip Knight
Fourth Official: Tony Mason