История группы началась в декабре 1994 года, когда трое одноклассников, Вячеслав Чифин (Чифа), Руслан (Руся) Захватошин и Кирилл (Киря) Журавлёв, решили совместно помузицировать. Дело происходило в городе Павлодаре, республика Казахстан, на дворе было морозно, а ребяткам было по 14 лет. Чифин бренчал на акустической гитаре, Захватошин извлекал душераздирающие звуки из китайской губной гармошки, а Журавлёв отстукивал корявый ритм руками по столу, на котором стояла металлическая подставка для книг, дребезжание её отдалённо напоминало звук рабочего барабана. Во время вышеописанной процедуры Киря напевал слова, которые тут же приходили в голову, и являлись в большинстве своём матерными. Благодаря двух кассетному магнитофону, включённому в режиме rec., 30 минут этого, с позволения сказать, сейшена, оказались записанными на плёнку. Чуваки, прослушав запись, решили, что это прикольно и, для придания ей статуса музыкального альбома, назвали эту запись «Натали’ 94», а новоиспечённый коллектив – группой Red Army.
Павлодарский период существования группы вряд ли стоит досконально описывать: ребята продолжали играть в рок-группу, состав её постепенно увеличивался и к 1997 году составлял 6 человек: Киря – гитара, вокал; Чифа – бас; Руся – вокал; Гришин Евгений (Джон) – вокал; Зайцев Виталий (Заяц) – ударные; Антон Журавлёв (Батон) – клавишные. Музыка группы представляла собой переигранные рок-хиты (как западные, так и русскоязычные), помноженные на отвратительные тексты, в основной массе оскорбляющие честь и достоинство различных знакомых людей.
