В штабе армии понимали еще и то, что отдельные нападения на склады и эшелоны Красной армии не решат проблему снабжения армии в долгосрочной перспективе. Героизм марковцев, равно как и героизм дроздовских и иных частей Добровольческой армии, добывал для нее все самое необходимое; люди жертвовали своими жизнями, чтобы хоть как-нибудь поддержать, казалось, всеми забытую, потерявшуюся в степях армию. Необходим был подход совсем иного свойства, и в штабе Деникина искали его, пока, наконец, не было признано целесообразным начать переговоры с правителем близлежащего Всевеликого Войска Донского генералом от кавалерии П. Н. Красновым. Став атаманом, генерал Краснов развил активную деятельность по развитию инфраструктуры и экономики казачьего государства. Войска ВВД составляли на середину 1918 года 17 тысяч человек; свои полки выставляла каждая станица. Были приняты на военную службу иногородние крестьяне, за что им жаловалось, от лица атамана, казачество и выделялась земля. Был брошен призыв к офицерству о возвращении в Донскую армию, что значительно укрепило ее иерархическую структуру и стало формировать казачьи соединения по принципам, принятым в императорской армии. Были созданы штабы придонских войсковых соединениях, и новая Донская армия стала выдвигать своих героев — генерала Мамантова, полковника Гусельщикова, молодого генерала Денисова, опытного бойца, генерала И. Г. Фицхелатурова, успешно воевавшего против красных частей Щаденко. На Дону, при старании Краснова, были введены военно-полевые суды, объявлена мобилизация 25 возрастов. Станичные пополнения сводились по нескольку в номерные полки, конница и артиллерия выделялись в конные и артиллерийские бригады, дивизии и корпуса. Казаки 1899–1900 годов рождения были определены Красновым в особые военные формирования, получившие название Молодой армии. На нее атаман возлагал особые надежды, ибо надеялся воспитать молодое пополнение в православно-самодержавном духе, свободными от крайностей революционной пропаганды, чем были еще значительно поражены казаки, вернувшиеся с Великой войны. По замыслу атамана им было суждено стать будущим ядром кадровой армии Дона, ее молодой гвардией…

Наряду с сухопутными силами на Дону создавался собственный флот, составленный из оставшихся маневренных пассажирских судов, которые обшивались стальными листами и на которых устанавливались соответствующие легкие орудия и пулеметы. В Таганроге из моряков Азовской флотилии был сформирован даже батальон береговой защиты. К лету 1918 года в составе Донского флота находились 3 морских и 5 речных судов, готовых к выполнению тактических боевых задач. В Новочеркасске открылось военное училище с рядом профильных направлений обучения, традиционных для военных училищ прежних лет, выпускавшее пехотинцев, артиллеристов, инженеров и кавалеристов. В короткий срок были открыты авиационные и офицерские школы, а также Донской кадетский корпус для детей донских воинов, павших в Великой и гражданской войнах. По соглашению с Германией, Дон поучил также некоторое число боеприпасов: 11 тыс. винтовок, 44 орудия, 88 пулеметов, 100 тысяч снарядов и десяток миллионов патронов. Для пошива форменной одежды была вновь пущена суконная фабрика, военно-ремесленные школы продолжили выпуск погон, фуражек, кокард, пуговиц и обуви для Донской армии.

Краснов распорядился внести дополнения и исправления в уставы и наставления бывшей Императорской армии, для подготовки их новых изданий с учетом практического опыта Великой войны и внедрении их в повседневную жизнь донского войска.

Именно с Красновым было необходимо начинать переговоры, ибо из всех располагавшихся на Дону сил, включая германские, донцы для Добровольческой армии оставались наиболее естественными и близкими по задачам союзниками. Прогерманская ориентация Краснова существенно отягощала взаимоотношения штаба Деникина и донского атамана. Генерал А. П. Богаевский подверг резкой критике заигрывания избранного атамана с германцами. Его стараниями первое письмо Краснова германскому императору было опубликовано и вызвало возмущение в военной и политической среде, а Кубанская Рада, упомянутая в этом письме как единомышленник, поспешила от него отказаться. Однако экономические соображения взяли верх над политикой, и Деникин командировал генерала Алексеева 15 мая 1918 года как главного концептуалиста движения на встречу с Красновым, в которой помимо них приняли участие кубанский генерал Александр Петрович Филимонов и генерал Африкан Петрович Богаевский в станице Маныческая. Встреча эта был прозвана в Добровольческой армии «Тильзитом». Краснов сразу же заявил Алексееву, что не в состоянии разрешить казакам полностью влиться в добровольческие вооруженные формирования, поскольку это может найти негативный отклик в Германии, отношениями с которой Краснов подчеркнуто дорожил. Более того, размещенные по соседству с территорией ВВД германские части ввиду такого поворота событий могли расценить слияние двух армий как потенциально опасное для своего присутствия в регионе, а провоцировать какие-либо вооруженные столкновения с германцами атаман не желал. На вопрос Алексеева «что же делать?», Краснов предложил: «…Дон даст средства, но тогда Добровольческая армия должна подчиниться мне». «Добровольческая армия, — парировал Алексеев, — Не нанимается на службу. Она выполняет общегосударственную задачу и не может поэтому подчиниться местной власти, над которой довлеют областные интересы». Краснов предложил в ответ добровольцам двинуться на Царицын, однако Алексеев практической цели подобного марша не понимал и попытался понять суть предлагаемого Красновым плана.

Идея атамана состояла в том, чтобы, придав Добровольческой армии донские части, стоявшие в Нижне-Чигирском и Великокняжеском районах, направить ее в Саратовскую губернию, где против большевиков начинались массовые волнения. На волне существующего народного гнева захватить у коммунистической власти контроль над артиллерийскими складами и заводами, закрепиться в промышленном центре и получить выход на воссоединение с уральскими казаками атамана Дутова.

При всей смелости и важности замысла Краснова Алексеев понимал, о чем он и сказал донскому атаману, что существует несколько соображений, по которым этот блестящий план на данный момент неосуществим: в тылу у добровольцев при их движении навстречу дутовским казакам останется 200-тысячная Красная армия, дислоцированная на Северном Кавказе. Случись этой силе ударить в тыл наступавшим на Царицын добровольцам, зажатая меж двух огней армия может погибнуть. Далее, указал Алексеев, главнокомандующий Добровольческой армией дал слово кубанцам, сражавшимся в его армии, что вернется на Кубань и поможет им очистить свою землю от большевиков. Кроме того, считая себя связанным союзническими обязательствами с Антантой, главнокомандующий Добровольческой армией считал себя не в праве, о чем просил Алексеева довести до сведения атамана, своим походом расчищать для германских частей дорогу к Волге и создавать на фланге Восточного фронта Антанты вероятную угрозу удара ее противника по Великой войне. Кроме того, объективно Добровольческая армия еще не была готова ко второму значительному походу по чисто техническим и человеческим соображениям: люди нуждались в отдыхе, а части Добровольческой армии еще нужно было переформировывать с учетом влившихся в нее в последнее время отрядов и отдельных войсковых подразделений белых ополченцев, партизан, казаков.