The hosts took an early lead when they were awarded a penalty, which Ildefons Sola Lima converted.
Bale drew the visitors level within 15 minutes, but had to wait until inside the final 10 minutes to add the winner.
Read how all the action unfolded below:
7.02pmGood evening! Wales's Euro 2016 qualifying campaign begins tonight, with a trip to European minnows Andorra. Chris Coleman has just named his starting XI, so let's take a look at the team news...
7.12pmAs expected, Chris Coleman has started Gareth Bale up front alongside Simon Church. There're plenty of experience in the rest of the lineup too, with the likes of Ashley Williams and Aaron Ramsey involved.
7.15pmA lot of the talk in the build up to this match has centred around the pitch. The Andorran FA have just opened their new national stadium, featuring an artificial 3G pitch. There has been some concern about the quality of the playing surface, which looks like it will cause some uneven bounce and unpredictable pace, but UEFA passed it suitable for this match last week.
7.17pmIt's quite a picturesque setting for the new stadium. The FA of Wales shared some shots from their training session on the artificial pitch earlier today:
7.19pmAndorra don't have the best record in qualifiers in recent years. The team have not won a match since beating Macedonia in a World Cup qualifier in 2004, while their last draw was the following year. In fact, it's been four years since the side scored a goal in a competitive fixture. The Welsh side will be hoping that they don't break that streak this evening.
7.22pmAccording to the latest FIFA world rankings, Andorra are the 52nd best team in Europe, with only San Marino ranked lower, although Gibraltar don't feature yet as they only played their first competitive match last night. Wales are 26th in Europe, and 41st in the world.
7.25pmWales's ranking puts them in an interesting position heading into the qualifying campaign. The top two sides in the group will automatically reach the finals, while third place goes into a playoff. UEFA has expanded the 2016 campaign from 16 teams to 24 teams, with Wales currently the third-highest ranked side in their team, but Israel and Cyprus will also be keen to press for the third place playoff spot, while Belgium and Bosnia start as favourite for the top two positions.
7.28pmThis will be the first time that Wales have faced Andorra in an international match. Given Andorra's recent run of defeats, anything but a comfortable win will be seen as failure for the visitors this evening.
7.31pmWhile Wales face what should be one of the easier matches of their qualifying campaign first, it gets trickier from here in. Next up, Bosnia will visit the Welsh side fresh from their first World Cup appearance. Three days later Chris Coleman's side face October, before completing 2014 with a trip to Belgium. However, Wales did hold Belgium to a draw when they met in the World Cup qualifiers last year.
7.34pmREFEREE WATCH! Slovenian official Slavko Vincic takes charge of this evening's match.
7.38pmThe players are making their way out of the tunnel ready for this evening's match. There's a decent amount of away support for Wales, with a similar number of red shirts in the crowd to home supporters. As with all internationals, the national anthems from both teams before kickoff.
7.42pmPREDICTION! While the pre-match formalities take place, there's just time for a prediction. With the likes of Bale and Ramsey facing Andorra, the home side really do need a miracle to get anything from this match. I can see Wales winning this 5-0 this evening.
2 minCHANCE! Wales look to catch their home side out with an immediate attack. Chris Gunter comes forward with a run down the right flank, but he doesn't fully catch his shot, leaving Ferran Poli with a comfortable save.
4 minThere's an early test for the Welsh defence as Ashley Williams is chased down by Ivan Lorenzo following an unusual bounce, but the captain managed to guide it back to Wayne Hennessey. The ball really has been moving quite unnaturally in the early stages of this match, it really doesn't look like the best pitch.
6 minNeil Taylor pulls Ivan Lorenzo down in the box to give the home side a spot kick.
6 minGOAL! Andorra 1-0 Wales (Ildefons Sola Lima PEN.)
6 minDefender Ildefons Sola Lima steps up to take the spot kick, and he sends Hennessey the wrong way, coolly slotting the ball into the right for his eighth international goal. That's stunned the travelling fans, who had been in fine voice up until then.
9 minWales don't look too concerned to have gone behind, they're still pressing but don't seem panicked. Gareth Bale has been kept pretty quiet so far, but Aaron Ramsey and Simon Church have been linking up quite nicely for Chris Coleman's team.
11 minAndy King makes a solid run into the box and looks to get a shot away for Wales, but Marco Valez times a sliding challenge perfectly to stop him unleashing his strike.
12 minBale tries to make his first real contribution, winning the ball near the corner flag before getting the better of Jordi Rubio with some stunning footwork, but the midfielder hacks him down to give Wales a free kick.
13 minCHANCE! Church flicks the ball on from the free kick before James Chester, who is making his full debut this evening, tries to volley to volley it home, but he slices the ball just wide.
15 minCHANCE! Bale is really starting to find his stride now, but it looks like Andorra have prepared well to face the world's most expensive player. He and Church exchange passes in the box before the latter takes a shot, but it's cleared. Bale quickly wins it back, but it's deflected behind for a corner.
17 minCHANCE! From the resulting corner, Bale wins the ball for a header, but nods the ball just inches over the crossbar. Wales are creating all the chances at the minute, but just can't quite find the finishing touch to get back on level terms.
19 minChester loses his footing as Martinez launches a counter-attack for the hosts, but Williams is ready to block his cross in, clearing it for a throw in.
22 minWales had been held up in midfield for a couple of minutes as Andorra fought to stem their dominant spell, but Ben Davies times a cross into the box superbly to pick out Bale, who beats Valez to head the ball in from near the penalty spot. The Wales supporters instantly burst back into life as the earlier blip seems to be behind the visitors.
25 minCHANCE! Wales have a chance to give themselves the lead for the first time this evening as Bale quickly wins another corner. Chester comes closest to heading it in, but he mis-judges his jump, allowing Andorra to make the clearance.
28 minAndorra push to restore their lead, winning a throw in near the corner flag, but Ashley Williams easily heads it clear. Ivan Lorenzo tries to play it back in for the home side, but Chester forces the ball out.
31 minWales are dominating the possession at the moment, with Gunter and Williams staying only just inside the Welsh half as the visitors try to pile on the pressure. However, King gives away a free kick when he charges into Josep Manuel Ayala just outside the Andorran box.
34 minWilliams mis-judges a long ball into the box, allowing Martinez to make a run in a bid to put the home side back in front, but the Welsh captain corrects his error just in time to get it clear. While Wales have had the majority of the possession and chances so far, Andorra are certainly causing a few problems when they manage to get in Wales's half.
37 minAndorra continue to enjoy a good spell as Carlos Eduardo Peppe makes a run towards the Wales goal, leaving himself with just Hennessey to beat, but he's flagged offside before he can unleash his shot.
40 minAndorra win a free kick when Ashley Williams brings down Martinez, which Maneiro floats in towards the Welsh penalty area, but Taylor is ready for it and makes the clearance. Wales have been a bit untidy for the last five minutes, they need to be careful not to give Andorra another chance to edge ahead in the final few minutes of this half.
43 minCHANCE! Gareth Bale comes close to adding a second for the visitors as Chester curls the ball in towards the Real Madrid forward, but he can't quite jump high enough to nod Wales in front.
45 minBOOKINGS! Tempers flare a little as half time approaches, with Joe Allen and Carlos Eduardo Peppe almost coming to blows, but their teammates step in to stop things escalating. However, the referee books them both for their actions.
8.33pmWell that certainly wasn't the half-time scoreline that was expected. Andorra have ended their four-year goalscoring drought to head into the break level with Wales in their opening Euro 2016 qualifier. The visitors needed a stunning header from Gareth Bale to get them level, but have looked vulnerable at the back at times.
8.37pmStatistically, Wales have been the stronger side. They had 74% possession in the opening 45 minutes, as well as twice as many shots as Andorra.
8.41pmThe penalty which gave Andorra the lead was actually awarded by the assistant referee behind the goal. Neil Taylor certainly seemed to have a handful of Ivan Lorenzo's shirt, so there can't be too many complaints from the visitors, although the Andorra midfielder certainly made the most of his fall.
8.44pmThe players are making their way back out ready for the second half.
46 minKICKOFF! The second half is underway, with Wales attacking the end which their away supporters occupy.
47 minWales immediately apply pressure inside the Andorra box, but play is stopped when Lima, who scored the opening goal of the night, picks up a head injury. Bizarrely, it looks like he's hurt himself while heading the ball clear.
49 minWales really do look focused at the start of this second half. Allen wins a corner when he sends in a ball for Church, which Garcia is forced to turn behind, but his delivery in from the corner flag is comfortable cleared by the hosts.
50 minThe Wales fans are unhappy as Peppe, who was booked at the end of the first half, goes in two-footed on Gunter, but the referee lets the midfielder off.
51 minPENALTY APPEAL! Wales want a spot kick as Christian Martinez and Chris Gunter tangle on the edge of the box, but the referee gives a free kick to Andorra instead, judging the Welsh defender to be at fault. Gunter isn't happy with the call as Martinez stays on the turf, and the officials have the step in as he tries to drag the defender to his feet.
53 minSUB! Andorra make their first change, and it's Carlos Eduardo Peppe who makes way, presumably to ensure that he does not get himself sent off as he does seem to be living a little dangerously. Marcio Vieira takes his place.
55 minAndorra get the ball inside the Wales half for the first time since the restart, and Ivan Lorenzo thinks that he is through on goal when an uneven bounce catches Williams out, but the midfielder is offside.
56 minCHANCE Wales win a free kick in a dangerous position when Andorra captain Lima collides with Bale just outside the box. The Real Madrid man lines up the set piece, but Poli comes across his goal to make a solid save.
58 minCHANCE! Bale quickly wins it back following Poli's parry, and he picks out Andy King with a well-timed cross, but the midfielder doesn't get his head fully on it, and it goes behind for a goal kick.
60 minBOOKING! Simon Church is the second Wales player to pick up a booking for catching Vieira with his arm while both were looking to win the ball in the air. Meanwhile, it looks like Chris Coleman is preparing to make a change.
61 minCHANCE! Bale picks up the ball 25 yards out and runs towards the Andorra goal, easily rounding Valez before unleashing a curling shot from the edge of the box, but it just misses the target.
62 minCHANCE! From nowhere, Andorra burst down the other end, resulting in Martinez trying to curl the ball in from the edge of the box, but it was always heading wide.
62 minSUB! The visitors make their first change, and it's Simon Church making way for Joe Ledley.
65 minBale tries to create another chance for Wales, crossing in from the left, but Emili Garcia blocks the effort, taking the ball straight in the face, and leaving him on the ground in quite some pain. Once play is back underway, Wales quickly force a corner.
67 minBale and Williams both look to turn it in from the corner, but Lima manages to get to it first and launches the home side on a counter-attack, but Ledley is back to halt their progress.
68 minBOOKING! Ivan Lorenzo is shown the yellow card after shoving Bale down in midfield.
71 minWales are continuing to see the majority of the ball, but Andorra's physical approach is doing just enough to keep the visitors out at the minute. Coleman still has the likes of Tom Lawrence and George Williams on the bench should he feel the need to inject some fresh legs up front.
73 minCHANCE! Wales have a corner, and it falls to Ledley just a couple of yards out, after Poli had already come off his line to punch clear, but Martinez was back on the line to divert it behind for a corner. The defender now appears to be hurt, delaying the resulting Welsh corner.
75 minBOOKING! Andorra quickly clearly the corner, with Allen and Marcio Vieira both chasing down the lose ball. The Crystal Palace player reaches it first, but is swiftly brought down by Vieira, who earns a booking for his trouble.
76 minSUB! George Williams comes on to make his first appearances in a competitive international for Wales, replacing Andy King. Wales have just less than quarter of an hour to find a winner against Andorra.
79 minAaron Ramsey charges into the Andorra penalty area as Wales are now desperately pressing for a winner, but the ball has too much pace and goes harmlessly to Poli.
81 minWales win a free kick in a dangerous position, and Gareth Bale lines it up. His effort is initially saved, but the referee rules that Riera encroached in the build up, giving the Real Madrid man a second chance, and he makes no mistakes with the second effort, expertly picking out the top right corner. What a relief for Wales!
83 minThe restart is slightly held up as the visiting supporters let their excitement get the better of them, crashing through an advertisement hoarding to end up on the pitch. Bale rushes over to urge them to calm down, and the stewards swiftly cart a couple of the more enthusiastic fans away.
83 minSUB! Martinez has to make way as he's been struggling since his clearance off the line earlier on. Oscar Sonejee takes his place.
86 minThere's a moment of concern for Hennessey as he comes out of the penalty area to take a free kick for the visitors, but he slices it poorly into the path of Riera, but Williams ensures that the Andorran striker doesn't get the shot away.
87 minThe Welsh fans are really enjoying themselves now as chants of "there's only one Gareth Bale" followed by a rendition of 'Land of My Fathers' fill the new stadium.
89 minWales are now just trying to keep the ball and run down the remaining few minutes to ensure that they do begin the campaign with a win. It certainly hasn't been the performance that had been expected.
90 minCHANCE! Aaron Ramsey comes close to making it a bit more comfortable for the visitors as Gunter makes a quick run down the right before crossing into the Arsenal midfielder, but Poli, who has had a good night between the posts, punches it clear. Meanwhile, there are to be six minutes of stoppage time.
90+2 minThere's a worrying sight for Wales and Arsenal fans right now as Aaron Ramsey is on the ground clutching his ankle. Both club and country will be hoping that's nothing serious, but Wales do have a sub left is necessary.
90+4 minSUB! Ramsey initially comes back on, although he's noticeably limping, so Coleman uses his final substitution to bring on Emyr Huws. It didn't appear to be contact, it just looked like the midfielder slipped on the artificial pitch.
90+5 minBOOKING! Marco Valez picks up a late booking after recklessly sliding into Gareth Bale.
9.39pmWales can breathe a huge sigh of relief as the referee blows the full-time whistle. Wales needed a brace from Gareth Bale as they come from behind to beat Andorra in their Euro 2016 qualifier.
9.42pmWell that's all from this match, but stick around for our match analysis and player ratings, as well as results from the rest of this evening's qualifiers. Thanks for joining me this evening, goodbye!