Холстинин и Кипелов остались в группе. В коллектив «Арии» пригласили басиста Дубинина и гитариста Сергея Маврина, совместно с барабанщиком Максимом Удалым.

Новый состав группы в 1987 году записал альбом, первоначальное название которого было «На службе силы зла». Этот альбом был выпущен государственной монополистической компанией «Мелодия», именно поэтому альбом потерпел многочисленные изменения: название было изменено на «Герой асфальта», обложка была соответственно заменена на другую, в добавок к этому в некоторых песнях были изменены тексты, не прошедшие цензуру. Из-за ограниченного объема пластинки, в конечный вариант альбома не вошли две песни «Легенды русского рока» и «Дай руку мне», эту песню впоследствии включили в сборник «Арии» «Штиль». Тираж третьего по счет альбома составлял 1 000 000 экземпляров, которые были все раскуплены в течении нескольких месяцев. Эта пластинка является лучшей в истории группы. Был создан видеоклип, первый для Арии, на песню из этого альбома «Улица Роз».

За период 1987-88 годов группа совершает гастроли по всему Союзу и делает первую свою поездку за границу, в Германию, где и выступила на фестивале «Дни стены» в столице, городе Берлин. Газеты их назвали «Казаками с гитарами» и «русскими Iron Maiden».

За это время и без того напряженные отношения с менеджером, окончательно были испорчены. Векштейн настаивал на новых концертных турах, а музыканты требовали записать новый альбом. Из-за этого конфликта в октябре 1988 года группу покидает Удалов. В ноябре к нему на смену взяли Александра Манякина. И всё же Удалов остается в Арии в качестве звукоинженера. Через год Ария выпустила новый альбом «Игра с огнем», в качестве их менеджера был Юрий Фишкин. Так как прошлый менеджер сохранил права на название группы, коллективу пришлось целый год выступать под названием «Ария-89». Виктор Векштейн так и не успел предъявить права группе и через год погиб.

В начале 90-ых годов группа снизила количество концертов, так как в стране начался экономический кризис. Музыканты были вынуждены начать поиск альтернативного дохода. Кипелов в те нелегкие времена подрабатывал сторожем, а Холстинин занимался частным извозом. После того как группа отпраздновала свой юбилей и выступила с несколькими концертами, она приступила к записи пятого альбома «Кровь за кровь», выпустили они его в 1991 году.

В 1994 году группа основала свою студию записи «ARIA Records» и подписала 5–летний контракт с «Moroz Records». С этим лейблом были переизданы в 1994 году все их пять альбомов. Художественным оформлением обложек занимался Василий Гаврилов.