Nazwa Nazwa Armia wpisuje się w stylistykę polskiego punka, gdzie częste są nazwy zawierające jedno dość krótkie dwu- lub trzysylabowe słowo i częste jest wykorzystanie głoski [r]. Można ją zaliczyć do mocno wykorzystywanej w punkowym nazewnictwie kategorii nazw związanych z agresją, wojskowością i wojną, które przewrotnie łączy się z antymilitarystycznym przekazem (podobnie jak np. Dezerter czy Fort BS). Początkowo Budzyński rozważał dłuższą nazwę Armia Zbawienia, jednak stanęło na krótszej formie preferowanej przez Brylewskiego, za to dodano człon Anti- odwracający wydźwięk. Nazwa z członem negującym była z traktowana jako nazwa dla wtajemniczonych – dla przyjaciół lub dla zmniejszenia kłopotów z cenzurą PRL. Obaj założyciele Armii przyznają się do autorstwa nazwy, Budzyński zaś twierdzi, że jest ona pochodną piosenki Niewidzialna Armia, co ma oznaczać armię duchową, która działa w ukryciu, nie zabijając, lecz czyniąc dobro.
Zespół czasem posługuje się logo będącym stylizowanym zapisem nazwy zespołu. Tusz, którym na kliszy Budzyński napisał ARMIA, projektując okładkę singla Aguirre, po wyschnięciu popękał w nieregularny sposób, dając specyficzny efekt graficzny.