Ifølge hans egen sleksthistoriske bok fra 1890 var han sønn av gårdbruker Thorvald Heyerdahl (1801–1881) på Nordre Haneborg i Aurskog og hustru Anne Sofie Andersdatter Haneborg, dattera til bygdas stortingsrepresentant Anders Halvorsen Haneborg (1767–1847). Anders var storebror til ingeniør Halvor Emil Heyerdahl (1840–1917). Han ble gift i 1862 med søskenbarnet Emilie Nicoline Frantzdatter.Blant deres barn var sangerinnen Halfrid. Forøvrig er Halfrid bestemora til jazzsanger Karin Krog (1937). Og han er også grandonkel til arkeologen Thor Heyerdahl (1914–2001).
Han fikk sin tidlige musikkundervisning hos faren, som selv hadde et lite orkester. Siden fikk han en bredere skolering hos Nils Ursin (1800–1862) og sønnen Fredrik Ursin (1825–1990) fra Ullensaker. Omkring 1860 var han elev i harmonilære hos den tyske komponisten Carl Arnold (1794–1873). Fra 1860 til 1862 var han fiolinist i Det norske Theaters orkester (etablert 1850 i Bergen). Han var også i en strykekvartett ledet av Johan Svendsen (1840–1911). Anders jobbet også tidvis som pianostemmer, men fra 1871 drev han hjemgården på Haneborg, men var lenge ufør i beina etter tømmerfløting, og det gikk da mere i genealogi og komposisjon.
Utover sine sonater og danser er han kjent for å ha skrevet ned en mengde viser og slåtter fra heimtraktene i Aurskog, såvel som Valdres og Hallingdal. Organisten og komponisten Ludvig Mathias Lindeman inkluderte flere av Heyerdahls innsamlede stykker som tillegg i sin samling Ældre og nyere norske Fjeldmelodier. Anders Heyerdahls verker er komponert i nasjonalromantisk stil, og til unionsoppløsningen i 1905 komponerte han den patriotiske Norsk Tappenstreg 1905, som straks ble publisert.
