Деникин часто говорил, что хочет найти баланс между правыми и левыми в политическом спектре. (У него было очень узкое определение левых и правых: социалисты и черносотенцы для него выходили за рамки.) В тревожные дни зимы 1920 года он обнаружил, что больше не может сохранять позицию, которая казалась ему центристской. Под давлением событий он шел на значительные уступки левым.

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

Смещение Лукомского было его первой уступкой. Лукомского особенно не любило подавляющее большинство казаков, которые винили его в непримиримо централистской политике Особого совещания. Генерал оттолкнул многих казачьих политиков своим оскорбительным поведением и бесцеремонными манерами во время долгих месяцев переговоров касательно казачьей автономии. Деникин выбрал Богаевского преемником Лукомского, чтобы получить поддержку казаков, но только частично достиг цели. Хотя это назначение было благосклонно принято умеренными, оно не задобрило сепаратистов, которые не любили Богаевского за его близкие отношения с лидерами Добровольческой армии.

С точки зрения Деникина, куда большей уступкой было его разрешение на отдельную армию Кубани. Этот вопрос ожесточенно дебатировался не один месяц, но Ставка всегда успешно сопротивлялась. Теперь Деникину казалось, что независимая армия может быть способна привлечь больше добровольцев, так что надо попробовать. Подавляющее большинство кубанских казаков сражалось в Кавказской армии, которая в январе 1920 года обладала наименьшей боеспособностью и наихудшей дисциплиной среди всех подразделений антибольшевистской армии. Это подразделение, которое разваливалось на части, должно было стать ядром Кубанской армии.

После перехода Врангеля в Добровольческую армию генерал Покровский принял командование Кавказской армией. Покровский, который в 1918 году играл огромную роль в формировании первой кубанской боевой силы и с того времени оставался важным участником событий на Кубани, стал отвратителен казачьим политикам из-за роли, которую сыграл в событиях в Екатеринодаре в ноябре 1919 года. Деникин избрал преемником покровского генерала Улагая, прекрасного офицера и цельной натуры. Однако Улагай был болен тифом, так что главнокомандующий назначил вместо него Шкуро. Это назначение не удовлетворило радикалов. Шкуро никогда не поддерживал сепаратистского движения и слишком тесно сотрудничал со Ставкой в прошлом. В общем, сепаратисты не признали за Деникиным право назначать командующего их армии. Они также возражали против договоренности, согласно которой в вопросах снабжения Кубанская армия останется зависимой от Ставки.

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

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

Сначала он описал военную ситуацию, которую воспринимал как угрожающую. Но он не утратил надежды, сказал он, потому что верит: большевики обессилены, плохо снабжены и страдают от слабой дисциплины. Затем он обсудил реорганизацию политических институтов. Он предостерег слушателей, что, если они решат формировать независимое государство, он покинет территорию вместе с остатками Добровольческого корпуса, русскими офицерами и многими из казаков. Он предрек, что такой шаг приведет к немедленному краху фронта и победе Красной армии. В заключение он подытожил свою программу:

«1. Единая, Великая, Неделимая Россия.

2. Донская и Кубанская армии составляют нераздельную часть единой русской армии, управляемой одними законами и единой властью.

3. Борьба с большевиками до конца.

4. Автономия окраин и широкая автономия казачьих войск, историческими заслугами оправдываемая. Широкое самоуправление губерний и областей.

5. Правительство, ведающее общегосударственными делами, из лиц честных, деловых и не принадлежащих к крайним воззрениям. Полное обеспечение в нем интересов казачьих войск вхождением казачьих представителей.

6. Представительное учреждение законосовещательного характера.

7. Земля — крестьянам и трудовому казачеству.

8. Широкое обеспечение профессиональных интересов рабочих.

9. Всероссийское Учредительное собрание, устанавливающее форму правления в стране».

Это было одно из самых левых заявлений Деникина. Он еще раз заявил о своей приверженности земельной реформе и после года колебаний пообещал Учредительное собрание. В этих вопросах, а также в неотложных проблемах построения государственной структуры Деникина и большинство мнений казаков теперь мало что разделяло. Однако воспоминания о прежней борьбе были еще свежи, и многие из слушателей не доверяли Деникину. Как указал в своем ответе Тимошенко, борьба за Учредительное собрание и земельную реформу — это хорошие лозунги, но их следовало бы представить раньше.

Переговоры по формированию нового правительства начались. От имени Деникина с представителями казаков договаривались Савич и Челищев. Обсуждение фокусировалось на шестом пункте Деникина, касающемся законодательного собрания. Казаки хотели, чтобы правительство несло ответственность за собрание и чтобы роль такого собрания временно исполнял Верховный круг. Было выработано компромиссное решение, которое позволяло Деникину накладывать вето на решения собрания, но представители могли преодолеть это вето по прошествии четырех месяцев при наличии большинства — двух третей. Роль законодательного органа будет играть временно сформированная комиссия. Половину членов комиссии выберет Круг, а вторую назначит Деникин. Военные решения и сообщение остаются в исключительной власти Деникина. Теперь Деникин перестал быть «диктатором» и стал «конституционным монархом».

4 февраля Круг принял проект только с двумя голосами против, и сложная задача построения правительства началась. Деникин назначил главой своего правительства Н. М. Мельникова, председателя правительства Дона. Для завоевания доверия казаков кабинет был составлен практически полностью из местных фигур. Эра Особого совещания определенно закончилась. Некоторых политиков, предложенных Мельниковым, Деникину было трудно принять. Особенно отвратительным главнокомандующий находил донского социалиста П. М. Агаева в качестве министра земледелия. Но Мельников доказывал, что участие Агаева даст поддержку левых, и Деникин сдался. Возможно, самый важный пост кабинета, военного министра, был отдан генералу Кельчевскому, начальнику штаба армии Дона. Генерал Баратов, который потерял обе ноги при покушении на жизнь в Тбилиси, стал министром иностранных дел. Это назначение показывает, что Деникин наконец понял значимость хороших отношений с государствами Кавказа. Основной пригодностью Баратова для этого поста были его хорошие связи в Грузии и Азербайджане. Деникин считал очень важным, чтобы портфель министра финансов оставался в руках человека, которому он полностью доверяет, так что М. В. Бернацкий стал единственным представителем Особого совещания. Самым примечательным выбором был Н. В. Чайковский, социалист со стажем и революционер, активно занимавшийся подпольной деятельностью с 1860-х годов. Чайковский стал министром без портфеля, а немного позже принял на себя руководство пропагандистской работой. Этот старик всегда играл значительную роль в антибольшевистском движении на Севере России. После поражения он бежал в Польшу и вернулся в Россию, чтобы присоединиться к Деникину, которому очевидным образом полностью не доверял или не симпатизировал, в момент, когда Добровольческая армия находилась на грани краха. Чайковский ненавидел большевиков так сильно, что был готов пойти на любые жертвы.