Из того же изначального материала, из того же биографического корня вырос сюжет первого романа — «Казенной сказки». Опубликованная в «Новом мире» (1994), она принесла писателю известность. Роман сразу же попал в шорт-лист Букеровской премии за 1994 год, что и послужило началом литературных споров о творчестве Павлова — с признанием одними и жестким неприятием другими критиками. Либеральная критика «приписала» Олега к «армейской теме» и почти десять лет держала писателя в «черном» «армейском теле», указывая на его «вторичность», «несамостоятельность», «чернушность» и т. д. Проза Павлова (и других писателей-традиционалистов) поставила перед всеми, желающими осмыслить литературный процесс 1990-х — конца XX века, сущностные вопросы: отношение к традиции великой русской литературы; проблему ценности реализма как художественного метода и умозрения в ситуации тотального разрушения принципов культурной иерархичности в постмодернисткой эстетике; понимание принципа народности в новых исторических условиях; вопрос об эстетическом «оправдании зла» и проблему нигилизма в современной литературе.
Так какой же традиции следовал Олег Павлов? Что полагал своими фундаментальными опорами? Для меня «Казанная сказка» — произведение в творчестве писателя центральное. Образ самого капитана Ивана Яковлевича Хабарова, такой живой и теплый, безусловно, принадлежит к образам классическим, потому как в его индивидуальности столько общего, что мы такими вот героями всегда и меряем свою национальную жизнь — как пушкинским комендантом крепости Иваном Кузмичем Мироновым, как толстовским Платоном Каратаевым, как солженицынским Иваном Денисовичем, беловским Иваном Африкановичем, распутинской Марией. Яркость их натуры тончайшем образом запечатлевается и в особой их «безликости», «всеобщности» — так в церкви миропомазание налагает особую печать на все без исключения лица. Так «солдатские черты делали его (капитана —
Сам писатель совсем не считал себя «разоблачителем» армейской жизни, он иначе понимал свою задачу: Павлов готов был отстаивать свои позиции, полагая, что русская литература всегда держалась «большими темами». Армия для него — это большая и трагическая «тема» современной русской литературы, только потому, что является живой «составляющей» современной жизни с ее войнами, с ее проблемами, в которые втянуты тысячи людей. И в «Казенной сказке» он будет говорить об этой типичной жизни, и смерти тоже типичной, и незаметном подвиге капитана Хабарова (главного героя повествования). Отдавая себе отчет в масштабе темы, писатель сражается за сочувствие к страданиям, угнетению, смерти даже и одного человека («Казенная сказка» будет трижды подряд переиздана).
Павлов писал и продолжает писать рассказы, публикуя их в «Новом мире», «Октябре», «Литературной газете», среди которых следует выделить рассказы «Митина каша» (Новый мир», 1995, № 10) и «Конец века»» («Октябрь», 1996, № 3). Оба рассказа замечены критикой, последний из них выделяется новой пронзительной интонацией — христианской жалости к выброшенному на дно жизни человека (Олег берет героем бомжа, но акцент делает не на его «грязи» и уродстве, а на первоначальном, красивом облике человека Божия). В 1997 г. публикует роман «Дело Матюшина» («Октябрь»), который продолжил размышления писателя о «казенном», «запертом» человеке. Критик Н. Елисеев в статье «Пятьдесят четыре» писал: «Олега Павлова волочит, тащит за собой инерция великой, но мертвой традиции. Народническая традиция Глеба и Николая Успенских, последним вершинным достижением которой был Андрей Платонов, а эпигонами, правда очень талантливыми эпигонами, — деревенщики, ныне мертва. Народнический пафос бухает в пустоту. Страдания и многотерпеливость русского народа нынче как-то не убеждают». Мне кажется, что нужно иметь удивительную эстетическую глухоту, чтобы Распутина и Абрамова, Белова и Астафьева видеть только эпигонами народничества Успенского. Критики, полагающие реалистическую традиции живой, плодотворной, видевшие в творчестве Павлова ее реальное и сильное воплощение, подчеркивали, что он «пишет не характер и судьбу. Он пишет органику рода. Или ее отсутствие, если род прерван, стерто начало и оставшаяся пылинка тщится продолжить себя и тем сохранить» (И. Борисова).