Wanderers’ winning run came to an end as Ryan Broom’s late goal handed the Whites just a third League One defeat of the season.
Ian Evatt’s men were within a couple minutes of claiming a point they would happily have gone home with after failing to fire at the Completely-Suzuki Stadium.
But a fourth successive clean sheet proved just beyond them as Broom struck with two minutes of normal time to go to give the rapidly rising Robins the points.
Wanderers remain in the top six but after four straight wins saw their momentum stall with a second away loss on a night their goal threat dried up.
And Evatt will be looking for a response and an improved performance when Wanderers return to Gloucestershire on Saturday to face Forest Green Rovers.
Wanderers made three changes to their starting line-up as Conor Bradley’s ever-present League One run was ended by the need for a breather after his early-season commitments for club and country.
Kieran Lee was also rested and Elias Kachunga made way for Jon Dadi Bodvarsson following the Icelander’s goalscoring cameo in Saturday’s win over Lincoln City.
There were few chances for Bodvarsson to add to his tally, however, in a first half largely controlled by Cheltenham.
The Robins had won their three previous home games and looked full of confidence as they attacked with pace and purpose to test Wanderers’ impressive defensive record.
No side in the division had conceded as few goals as the Whites and despite having to deal with a succession of balls into their box, Evatt’s men - with George Johnston again a pillar of strength at the back - hung on to the break break with James Trafford’s goal intact.
Trafford was tested only once as he kept out a skidding effort from Taylor Perry but there were goal threats from the lively pair of Ryan Jackson and Dan Nlundulu before Wanderers eased the pressure with a couple of openings of their own.
The Whites – who could well have had a penalty inside the first minute when Dion Charles was bundled over – made inroads down the right-hand side where Gethin Jones combined with Will Aimson on his first league start since mid-August.
One break from Aimson ended with a low cross and an effort from George Thomason which the midfielder dragged wide.
And then when Jones delivered just before half-time, the ball just eluded Bodvarsson and Charles as they hovered on the six-yard line.
Wanderers needed to do more, however, and with an hour gone Evatt made a decisive move to try and reverse the flow as he sent on Dapo Afolayan and Kieran Sadlier to get the Whites on the front foot.
Afolayan immediately forced a couple of corners but it was Cheltenham who almost went ahead through a corner of their own.
That followed a brilliant save by Trafford to keep out a Lewis Freestone header with a finger-tip save at the expense of the set-piece which Sean Long met with a header cleared off the line by George Thomason.
Again, Evatt reacted positively with three further changes and Wanderers looked as though they might find an opening on the break.
But they still couldn’t get a clear sight of goal and with two minutes of normal time to go Cheltenham were the ones to make the breakthrough to grab a deserved winner when Nlundulu lifted the ball through perfectly for Broom to nip in and steer home to decide the outcome.
Wanderers: Trafford; Aimson (Sadlier 61), Almeida Santos, Johnston; Jones, Williams, Thomason (Morley 72), Iredale; Dempsey (Afolayan 61); Charles (Kachunga 70), Bodvarsson (Bakayoko 70). Substitutes: Sheehan, Beck.
Booked: Williams, Thomason
Cheltenham Town: Southwood; Long, Taylor, Freestone; Jackson, Sercombe, Perry (Williams 79), Ferry (Bonds 79); Broom; Nlundulu, Norton (Lloyd 84). Substitutes: MacDonald, Williams, Bradbury, Brown, Adshead, Bonds.
Booked: Norton, Jackson
Referee: Gavin Ward