Scottish frontman Graham rose highest to glance home a Tom Smith free kick just before the break at the Jubilee Stadium.
The Robins had also inside the first 30 seconds of the fixture when a trialist powered home a right wing cross for a dream start.
Midfielder Ben Tozer came closest in the second half with his powerful shot crashing back off the crossbar.
Manager Gary Johnson named a team with a mix and experience, with the home clash with Birmingham City just two days later.
And on a hot and sunny night, it was the visiting Robins who were ahead within the first minute as a right wing cross was powerfully headed home by trialist.
Both goalkeepers were quickly called into action after ten minutes as Rhys Lovett denied Sean Brain with a fingertip stop before George Lloyd used all his pace to get in behind but Harvey Rivers stood tall.
Archie Brennan then broke the offside trap down the right wing and his cross found Smith, but his shot was smothered by the alert Rivers.
The home stopper then denied Graham from 25 yards out before Smith unloaded a fierce drive that whistled just over the Evesham bar.
Evesham went close themselves on 35 minutes when Brain broke away and rolled a shot past Lovett that hit the right hand post and bounced away.
Cheltenham duly responded and went further ahead when Smith's neat free kick found Graham who made no mistake from six yards out.
Academy prospect Will Dawes was a half-time substitute for Cheltenham, as they looked to keep momentum going as temperatures started to drop.
And they nearly made an ideal start when Lloyd raced got down the right but his low ball was just behind a stretching Graham in the middle.
The Robins emptied the bench with 20 minutes to go with nine changes, as only Dawes and Lovett stayed on.
And it was Dawes who had the ball in the net in the final quarter, only for the flag to see the goal ruled out.
Evesham came close again ten minutes from the end when Marley Thomas saw his deflected shot saved by the ever alert Lovett.
Cheltenham finished the game the strongly and rattled the bar late on through Tozer.
Evesham: Rivers, Campbell, Tunnicliff (Middleton 84), Haskayne (Colicutt 65), Summers (Hancock 45), Wellon, Price (Dunbar 66), Williams (Turley 45), Brain (Tucker Davies 45), Brown (Davies 45), Thomas.
Robins: Lovett, Thomas (Handley 70), Bower (Mullins 70), Forster (Boyle 70), Duncan (Debayo 70), Smith (Atangana 70), Brennan (Tozer 70), Briscoe (C Thomas 70), Lloyd (Broom 70), Graham (Price 56 (Addai 70)), Trialist (Dawes 45 (Price 89)).
Referee: Ravel Cheosiaua
