Craig Woodman scored one and made one as Brentford progressed to the Second Round of the Carling Cup for the first time since 2007.
The left back set up Robbie Simpson for a goal on his full Brentford début and then added the second minutes later.
On a slick pitch, getting gradually wetter through the first half as the rain fell, Brentford produced a performance full of attacking verve for an hour.
They created chance after chance, hit the woodwork twice, and once they got ahead through Simpson there seemed little doubt they would win.
But Cheltenham hit back and piled the pressure on in the later stages, which lead to a few nervous moments for the home side.
The Bees will probably feel they should have had more than two goals in the first hour - Marcus Bean failed to control a Nicky Forster cross when 15 yards out and soon after the midfield man had a shot tipped over by Scott Brown.
In between times the goalkeeper almost presented Brentford with the opener, a low Woodman cross was turned towards goal by Forster and Brown just about scrambled it around the post, nearly turning it into the net.
At the other end, with the rain pouring down, a long ball forward from Danny Andrew wasn't held at the first attempt by Simon Moore, who recovered in time to stop it going over the line.
Cheltenham took it as a sign to have pot shots at the young stopper and he did well to hold a low Frankie Artus drive.
Moore also tipped a Josh Low shot wide but most of the action was at the other end.
Karleigh Osborne headed against the bar when Simpson nodded down a Woodman corner and Forster failed to turn in from eight yards when a poor clearance fell to him.
Forster looped a header wide soon after as the chances continued to come in the first 15 minutes and after a mini lull, the last twenty minutes of the first period saw The Bees produce attacking football that would have graced any game.
Jeff Goulding shot wide for Cheltenham but their forays forward were becoming fewer and further between.
Gary Alexander shot wide at the near post for Brentford and a low Simpson shot was blocked superbly by Andrew.
From the resulting corner Legge crashed a header against the crossbar and although it looked as if it may have dropped over the line it wasn't given.
But the opening goal was coming and duly arrived just past the half hour when Woodman exchanged passes with Sam Wood and swung over a beautiful cross, Simpson arrived late and nodded in from close range.
Cheltenham almost equalised immediately when an Andrew shot was deflected over but ten minutes before the break Brentford had a second.
Woodman curled in a free kick from the left, Pim Balkestein jumped in front of Brown, the ball by-passed them both and ended in the far corner.
Alexander miss-hit a shot from 10 yards after Simpson got in behind and then fired a shot narrowly over on the turn from 20 yards as Brentford threatened to run riot.
The half time whistle probably came as a relief to Cheltenham although Moore did have to make a save late in the first 45 from a curling Michael Pook free kick.
The second half started as the first had ended and although Cheltenham had some possession the first 15 minutes was pretty much all Brentford.
Forster diverted an Osborne cross narrowly over, Simpson headed narrowly wide and Alexander missed the target from 20 yards after a nice turn.
But on the hour mark - against the run of play - Cheltenham had a lifeline.
Artus fired in a fierce long range free kick that Moore saved but could not hold and Shaun Jeffers turned it in.
Junior Smikle headed wide soon after as Cheltenham started to sense there could be life in the tie, something that appeared unlikely for the first hour.
Brentford knew a third would wrap it up and went looking for it - Simpson fired a half volley narrowly over and after a fine move involving Alexander and Charlie MacDonald the wide man cut inside and forced a save from Brown.
But Cheltenham were far from done, a Smikle shot from a tight angle was punched out by Moore and Legge made a vital block from a Jeffers volley.
Wood forced a low save from Brown after a burst forward and when he swung over a cross moments later MacDonald saw a header cleared off the line by the scrambling goalkeeper and central defender Martin Riley.
Balkestein headed a late Woodman corner over as it appeared Brentford had weathered the storm.
And despite a late stoppage time flurry, they had.
Brentford: Moore; Osborne, Legge, Balkestein, Woodman; Simpson, O'Connor, Bean, Wood; Forster (sub MacDonald 64 mins), Alexander
Subs (not used): Lee, McCracken, Blake, Saunders, Spillane, Hunt
Cheltenham Town: Brown; Lowe, Riley, Elliott, Andrew; Pook; Low (sub Melligan 73 mins), Artus; Smikle; Goulding (sub Shroot 75 mins), Jeffers
Subs (not used): Lee, Bird, Gallinagh, Lloyd-Weston, Watkins
Attendance: 2,049 (146 away fans)
By Chris Wickham