Печатается как прозаик с 1965 года. В 1967 году завершил роман «Степан Сергеевич», который был анонсирован журналом «Новый мир» на 1968 год. Однако из-за противодействия цензуры роман появился на журнальных страницах лишь 20 лет спустя («Новый мир», 1987, №№ 7–9) и сразу принес автору успех, поддержанный почти одновременной публикацией романа «Затяжной выстрел» в журнале «Знамя» (1987, №№ 10–11).
Азольский был членом союза писателей СССР, Русского ПЕН-центра, членом международной ассоциации писателей баталистов и маринистов. Его романы, повести и рассказы переводились на немецкий, польский, эстонский и китайские языки. В критике отмечалось умение Азольского создать авантюрное повествование на материале советской эпохи, открытие им нового типа персонажа — героического одиночки, отстаивающего своё право на жизнь в ситуации усугубляющегося, спровоцированного идеологией абсурда. Проводились параллели между прозой Азольского и литературой абсурда, произведениями Грэма Грина (Евгений Ермолин). По произведениям А.Азольского сняты популярные фильмы и сериалы: «Диверсант», «Забытый», «Степан Сергеич», «Неизвестные страницы из жизни разведчика». Азольский писал и печатался до конца жизни — в февральском «Новом мире» за 2008 год опубликован его рассказ «Предпоследние денёчки».