Jesienią 1989 roku Armia zagrała pierwszy zagraniczny koncert. Było to w Berlinie na festiwalu zespołów bloku wschodniego – oprócz Armii wystąpił Tilt oraz zespoły z NRD i ZSRR. Armia została tam zaproszona przez zespół Die Firma, który w tym czasie coverował Niewidzialną Armię. Kolejne zagraniczne koncerty odbyły się w trakcie trasy po Czechosłowacji w grudniu 1990 roku, kilka miesięcy po występie na ostatnim wydaniu Róbrege. Legenda przyniosła zespołowi dużą popularność, nie tylko w środowisku punkowym, ale także na szerzej rozumianej scenie rockowej, a nawet popularnej. W tym czasie Armia określana była jako jeden z najwybitniejszych polskich zespołów rockowych. Zespół miał wystąpić na festiwalu w Opolu w 1992, jednak ze względu na kontrowersje związane z ówczesnym organizatorem, firmą Brawo, znaną z piractwa fonograficznego, jak również promocji disco polo, wraz z kilkoma innymi wykonawcami odmówił udziału. Na koncerty Armii przychodziło też wielu skinheadów, co często kończyło się rozróbą, a nieraz przerwaniem koncertu. Ten typ publiczności, podobnie jak niektóre skłonne do bójki grupy punków, był piętnowany przez zespół, co czasem kończyło się odwetem.