The home side took a surprise lead when Wales gave away a penalty early on, but two goals from Gareth Bale sealed all three points for the Welsh team.
Ildefons Sola Lima's sixth-minute penalty ended a four-year goalscoring drought for the Andorrans.
Here, Sport Mole takes a closer look at the outcome.
On target: 1
On target: 5
Was the result fair?
Given the number of chances that Wales created and their vastly superior possession, the result was absolutely fair. Chris Coleman's side's struggles have largely been attributed to the pitch by pundits and fans, while the home side were lucky to finish the match with 11 men following a string of rash challenges from the Andorran players.
Andorra made an impressive start to the match. They made the most of their early opportunity from the penalty and defended superbly to limit Wales's early chances, keeping Gareth Bale pretty anonymous for the opening 15 minutes. They faded towards the ends of the match though, and were forced to turn to a rather messy, physical approach to stop Wales added to the scoreline late on.
Wales looked the better of the two sides from the start, falling behind because of a basic error at the back despite a bright start, but they continued to create chances and control the tempo of the match throughout. At times, the visitors looked somewhat stretched at the back, with communication between the back four clearly a bit lacking, while the pitch got the better of Ashley Williams a few times, but on the whole it was a solid display from the Welsh side.
Sports Mole's man of the match
Gareth Bale: The world's most expensive player was worth every penny for Wales tonight, scoring both of their goals, including a spectacular free kick inside the final 10 minutes to seal all three points. Given the concerns about the pitch, Bale had not been expected to play the full 90 minutes, but the forward continued to create chances and ran at the Andorra defenders deep into stoppage time despite being on the receiving end of several dubious challenges.
Neil Taylor's early shirt grab on Ivan Lorenzo put Wales in a position that they should never have been in, giving the home side a penalty inside the opening 10 minutes. While the Andorra defender made the most of the foul to make sure he got the spot kick, it was a silly mistake by the Swansea City defender, leaving Wales on the back foot for the majority of the night.
Slovenian official Slavko Vincic will probably want to forget some of the decisions he made this evening. Compared to the challenges that he booked Joe Allen and Simon Church for, some of the Andorra players were lucky not to be sent off, particularly Carlos Eduardo Peppe, who went unpunished following a two-footed challenge on Gareth Bale after already earning a yellow. Wales will also argue that they should have had at least one penalty in the second half, while he initially had ruled wave on to the Andorra spot kick only to be corrected by one of his assistants.
Andorra: Andorra will face Group B's top-ranked side, Belgium, next month.
Wales: Wales will be back on home soil in their next qualifier, facing Bosnia-Herzegovina on October 10.