Andorra hade bedövat Chris Colemans sida genom att ta en sjätte minuts ledning genom Ildefons Limas straff, Andorras första konkurrensmål sedan 2010.
Bale ledde Wales nivå 16 minuter senare, men det skonade inte Coleman hånarna av de rasande resande walesiska fans som poängen förblev 1-1 vid halvtid.
Wales sökte desperat efter en vinnare, och deras försvar kom så småningom efter 81 minuter när Bale böjde sig i en vacker frikick för att förneka Andorra en första tävlingspoäng i nio år.
Även om en seger av något slag var välkommen, den walesiska föreställningen var tydligt föga övertygande eftersom de syftar till att kvalificera sig för finalen i en stor turnering för första gången sedan 1958 års VM.
Det hade varit optimism som ledde fram till denna kampanj, med Euro 2016 expanderade från 16 till 24 lag för första gången och Wales dras tillsammans med Bosnien, Belgien, Israel, Cypern och Andorra i sin kvalificering grupp.
Wales kunde knappast ha bett om en snällare öppningsfixtur - en resa till en Andorranisk sida som rankas 199th i världen, 158 platser under dem i ställningar, och har förlorat sina senaste 44 tävlingsspel.
Men till Wales fasa verkade utsikten till en första tävlingsvinst för Andorra sedan 2004 vara nyktra verklig när värdarna tog en oväntad ledning.
Eftersom Wales inte kunde klara sig från ett långt Andorranskt kast, ansågs Neil Taylor ha dragit Ivan Lorenzos skjorta.
Uttryckt av Mitja Zganec - den extra biträdande domaren bakom målet - Slovensk domare Slavko Vincic pekade på platsen och Andorra kapten Lima lugnt konverterade genom att skicka Wayne Hennessey på fel sätt.
Medan Wales resekontingent på ca 1500 för en kort stund tystades, vrålade den andra halvan av den 3.300-kapaciteten Estadio Nacional i att inte tro på hänryckning.
Leden varade bara 16 minuter, som Bale på väg in i nedre hörnet från ett lockande kors från vänster-back Ben Davies.
Bale hade oundvikligen varit fokus för förmatch uppmärksamhet, med £ 85m Real Madrid ytter förväntas börja som centrum framåt.
Coleman valde istället världens dyraste fotbollsspelare på sin gynnade högra flank, men han visade målsättning instinkt av en naturlig strejkare till nicka Wales nivå.
Besökarna åtnjöt nästan total dominans över innehavet, om än lite ostadigt ibland när spelarna bekantade sig med den oberäkneliga studsen av Andorras kontroversiella 3G-plan.
Med den konstgjorda ytan gummi pellets flyger upp varje gång bollen slog marken, Wales gjorde hårt arbete för att skapa äkta poäng möjligheter.
Efter att ha buats av fältet på halvtid, Coleman försökte ta initiativet genom att byta till en 3-5-2 formation i början av den andra halvan.
Det var mer brådskande att den walesiska föreställningen efter omstarten, och Bale var katalysatorn för förändringen i tempot.
Han hade en frikick från avstånd räddad av Ferran Pol och en långdistans ansträngning som fizzade precis brett, medan hans kors leddes vida av Andy King.
Det fanns tillfällen då Wales desperation att ta ledningen ledde till en förlust av form och rytm, eftersom spelarna kämpade för att anpassa sig till taktiska förändringar.
Coleman fortsatte att tinker - ersätta sin enda strejker Simon Church med mittfältare Joe Ledley att lämna Bale som den mest avancerade spelaren i en makeshift attack.
Och när genombrottet så småningom kom, var det ingen överraskning att Bale återigen var frälsaren.
Efter att George Williams hade blivit bortskämd 25 meter från målet, piskade Bale bollen briljant bortom Pol för att bespara Coleman och hans sida en stor förlägenhet.
I den enda andra matchen i grupp B på tisdag förlorade Bosnien 2-1 hemma till Cypern.
Matchen slutar, Andorra 1, Wales 2.
Andra halvlek, Andorra 1, Wales 2.
Marc Vales González (Andorra) visas det gula kortet för en dålig foul.
Gareth Bale (Wales) vinner en frispark på vänster flygel.
Foul av Marc Vales González (Andorra).
Ersättning, Wales. Emyr Huws ersätter Aaron Ramsey på grund av en skada.
Foul av George Williams (Wales).
David Maneiro (Andorra) vinner en frispark i den defensiva halvan.
Försening över. De är redo att fortsätta.
Försening i match Aaron Ramsey (Wales) på grund av en skada.
Foul av George Williams (Wales).
Ildefons Lima (Andorra) vinner en frispark i den defensiva halvan.
Joe Ledley (Wales) vinner en frispark på vänsterflygeln.
Oscar Sonejee (Andorra). - (EN) Herr ordförande!
James Chester (Wales) vinner en frispark i den defensiva halvan.
Foul av Marcio Vieira (Andorra).
Substitution, Andorra. Juli Sanchez Soto ersätter Josep Ayala.
Offside, Wales. Aaron Ramsey försöker en genom boll, men Gareth Bale fångas offside.
Joe Allen (Wales) vinner en frispark i den defensiva halvan.
Foul av Gabi Riera (Andorra).
Substitution, Andorra. Oscar Sonejee ersätter Cristian Martinez.
Mål!  Andorra 1, Wales 2. Gareth Bale (Wales) från en frispark med en vänster fotad skott till övre högra hörnet.
Gabi Riera (Andorra) visas det gula kortet.
George Williams (Wales) vinner en frispark i anfallshalvan.
Foul av Ildefons Lima (Andorra).
Ersättning, Wales. George Williams ersätter Andy King.
Marcio Vieira (Andorra) visas det gula kortet för en dålig foul.
Joe Allen (Wales) vinner en frispark på vänsterflygeln.
Foul av Marcio Vieira (Andorra).
Försening över. De är redo att fortsätta.
Försening i match Cristian Martinez (Andorra) på grund av en skada.
Hörnet, Wales. Förföljd av Josep Ayala.
Försök blockerat. Gareth Bale (Wales) huvud från mitten av rutan är blockerad. Hjälpt av Ben Davies med ett nyckelkort.
Hörnet, Wales. Förföljd av Ildefons Lima.
Foul av Joe Allen (Wales).
Cristian Martinez (Andorra) vinner en frispark i den defensiva halvan.
David Maneiro (Andorra) visas det gula kortet.
Aaron Ramsey (Wales) vinner en frispark på högerkanten.
Cristian Martinez (Andorra). Ordförande
Hörnet, Wales. Förföljd av David Maneiro.
Gareth Bale sent fri-kick räddade Wales från förlägenhet i Andorra som hans två mål gjorde det till en vinnande start på deras Euro 2016 kvalificerande kampanj.