Начиная с 1925 года, того года, который Артём Весёлый отмечал как время, когда он «начал писать книгу», он ежегодно, а иногда и по нескольку раз в год, ездил на Кубань, беседовал с сотнями рядовых участников мировой и гражданской войн, знакомился с архивными документами в крайистпартах, а зимой 1926 года в труднейших условиях повторил путь отступления Одиннадцатой армии через астраханские пески.
В 1927 году была закончена глава «Пирующие победители», дополнившая роман эпизодами о банде Ивана Черноярова, в 1928—1931 годах — «Чёрный погон», «Над Кубанью-рекой», и «Горькое похмелье». По мере написания главы печатались в периодических изданиях и были включены в отдельные сборники рассказов Артёма Весёлого.
План и композиция книги складывались постепенно, в процессе её написания, так как в основе романа лежала не строгая сюжетная линия, а характерные картины и события того времени, образы людей, самоотверженно сражавшихся за высокие идеи Октябрьской социалистической революции, а также врагов революции, которые в своём кулацко-анархическом буйстве затрудняли или противостояли борьбе Красной Армии с белогвардейцами. И каждая новая часть вносила свои коррективы и сюжет и композицию.
В 1926 году Артём Весёлый, составляя план романа, разделил его (тогда ещё носившего название «Похождения рядового солдата Максима Кужеля») на десять глав — «залпов». Год спустя было найдено и окончательное название романа — «Россия, кровью умытая». Время шло. Количество глав увеличилось до двенадцати. Тем самым писатель расширил границы своей книги. «Место действия,— писал он в неопубликованном предисловии к „России, кровью умытой“,— фронт империалистической войны, Москва — Петроград на фоне 1917—1918 годов, Кубань — Волга — Украина, пролетарские центры и уездная Россия, фронт и тыл революции и контрреволюции, поток событий…»
В 1932 году Артём Весёлый начал подготовку написанной части романа к изданию отдельной книгой. Многочисленные, опубликованные под разными названиями, отрывки он объединил в семь глав, составивших первую часть произведения. Для второй же части был переработан текст повести «Страна родная».
Кроме отдельных глав, в состав «России, кровью умытой» были включены «Этюды к роману». Они явились весьма своеобразным компонентом в общей композиции романа. По замыслу автора, вся книга должна была состоять из 24‑х глав. «После каждых трёх глав,— писал он в одной из своих заметок,— как продух или пауза музыкальная, идут семь этюдов. Этюды — это коротенькие, в одну-две-три странички, совершенно самостоятельные и законченные рассказы, связанные с основным текстом романа своим горячим дыханием, местом действия, темой и временем…»