10th cent. Uncertain etymology. Typical proposals are Vulgar Latin *ambitare (from Latin ambitus) or *amlare (from ambulare "to amble") or *adnare (from Latin adnare "to swim," "to approach"). All reconstructions are fraught with difficulties. Further, the Old Spanish perfect andide (modern Spanish anduve) was irregular and could not conceivably derive from ambitus, which was a regular perfect. While *adnare is more persuasive from a phonological perspective, it is a semantic stretch. For the etymology of ambulare, see amblar.
Latin adnare derives from ad- "toward" (see a(d)-) and nare "to swim" (see nadar).
In spoken Mexican varities, and to a lesser extent in Spain, andar is used with the gerund in place of estar (e.g., ¿Qué andas haciendo? "What are you doing?").
Asturian andar, Portuguese andar, Galician andar, Catalan anar, Occitan anar
There are few true cognates and all highly localized to a small geographic region, as all other forms derive from Latin ambulare (including Portuguese and Galician). Thus the ancestor of andar, whatever it might have been, was a highly-regionalized innovation in Vulgar Latin.