1965–1976 m. mokėsi Kauno 4-ojoje vidurinėje mokykloje. Mokykliniais metais dešimtmetį dainavo chore "Varpelis", dalyvavo kuriant muzikinių spektaklių fonogramas, 1972–1975 m. buvo grupės "Amžinas remontas" vokalistas. Įsitraukęs į teatrinę veiklą, A. Navalinskas dalyvavo pirmajame Giedriaus Kuprevičiaus spektaklyje miuzikle "Ugnies medžioklė su varovais" (1974–1976 m.), kur dainavo vieną iš pagrindinių Juliaus partiją.

1976–1977 m. jis studijavo Kauno politechnikos instituto Mašinų gamybos fakultete inžineriją, bet studijas paliko.

1977–1978 m. A. Navalinskas buvo Kauno jaunimo muzikinės studijos (vadovai Stanislovas Rubinovas ir Giedrius Kuprevičius) narys, 1978–1980 m. – Juozo Vaitkaus studijos Kauno dramos teatre narys.

1980–1988 m. (nuo 1982 m. – neakivaizdžiai) jis studijavo Lietuvos konservatorijos Klaipėdos fakultetuose, įgijo teatro režisieriaus išsilavinimą.

Nuo 1982 m. iki šiol A. Navalinskas gyvena ir dirba Anykščiuose.

1982–1991 m. jis buvo Anykščių kultūros rūmų Liaudies teatro režisierius, nuo 1991 m. dirbo teatro "Agnis" režisieriumi, kasmet su kolektyvu pastatydamas po du naujus spektaklius. Nuo 1989 m. jis taip pat buvo humoro grupės "Krakatūzai" vadovas. 1993 m. A. Navalinskas Anykščiuose pradėjo organizuoti jaunųjų talentų konkursus "Ateik, kol nevėlu". Prie teatro jis įkūrė moksleivių dramos studiją, kurioje išugdė ir aktorę Dalią Michelevičiūtę.

1997–2020 m. A. Navalinskas buvo Anykščių Jono Biliūno gimnazijos teatro mokytojas ir dramos studijos vadovas, gimnazijos bendruomenės ir moksleivių teatrų spektaklių režisierius. Jis inscenizuodavo įvairius literatūros kūrinius ir režisuodavo moksleivių teatro pastatymus, su jais dalyvaudavo teatro konkursuose, rengdavo labdaros spektaklius. Šioje studijoje jis išugdė aktorę Tomą Razmislavičiūtę.

Kauno mažajame teatre jis režisavo spektaklį Joe Ortono "Šalutiniai simptomai" (1999 m.). Jis sukūrė grafo fon Danenbergo vaidmenį operoje džiazo motyvais "Šventavartė" (režisierė Galina Germanavičienė, Anykščių – 2012-ųjų Lietuvos kultūros sostinės pastatymas, 2012 m.).

Buvo vedęs, išsiskyrė. Sūnūs: Mantas Navalinskas (g. 1978 m.) – architektas ir Tauras Navalinskas (g. 1979 m.).

Vėl vedė 1987 m., žmona Violeta Garšvaitė-Navalinskienė (1960–2012) – muzikos pedagogė, chorvedė. Liko našlys. Sūnus Vytis Navalinskas (g. 1988 m.).