Прибыв в Екатсринодар, Алексей Николаевич быстро свел там знакомство со многими политическими деятелями и военными, среди которых были и такие известные добровольческие офицеры, как А.Г. Шкуро и B.JI. Покровский. С последними Гришин-Алмазов, видимо, хорошо покутил, так как на следующее утро пребывал «в несколько расстроенных чувствах».
Один из «екатеринодарских» политиков, конституционный демократ М.М. Винавер так вспоминал потом об этих днях из жизни генерала:
«Невысокий, хорошо сложенный, всегда чисто выбритый, с правильными, энергичными чертами лица, с властными жестами, Гришин-Алмазов явно позировал на Наполеона. Только слишком он был речист и слишком хвастлив для Наполеона. В первый же день [знакомства] он предложил мне пригласить нескольких друзей, чтобы выслушать его рассказ о Востоке, и предупредил при этом, что если он будет говорить по четыре часа в день, то рассказ будет длиться чуть ли не целую неделю... .Все мы после первого сеанса почувствовали, что второй уже будет бессодержателен и скучен. На этом втором сеансе и оборвались собеседования».
Антон Иванович Деникин, ничего не знавший о Гришине, встретил его весьма сдержанно. Позднее он писал о нем: «Я познакомился с ним в конце 1918 года, когда судьба заставила его покинуть Сибирь и появиться в Екатеринодаре. Молодой, энергичный, самоуверенный, несколько надменный, либерал (быть может, более политик, чем воин, с большим честолюбием и с некоторым налетом авантюризма), он несомненно сыграл бы большую роль в сибирском движении, если бы в самом начале своей карьеры не переоценил свой вес и влияние».
Но доклад Гришина о положении в Сибири произвел на Деникина благоприятное впечатление и, видимо, не зная, как с ним поступить, он решил пока командировать его в Румынию, с информацией об обстановке в Омске и вообще на востоке страны.
В это время в румынских Яссах открывалось так называемое Ясское политическое совещание между военными и дипломатическими представителями держав Антанты и США, с одной стороны, и русской делегацией — с другой. Совещание, учитывая поражение Германии и Австро-Венгрии в мировой войне, должно было выработать конкретные условия помощи союзников русским противоболыпевистским силам и наметить меры к восстановлению России. Одним из первых шагов в этом направлении была разработка программы политических и военных действий в Малороссии и Новороссии, оккупированных к тому времени австро-немецкими войсками. Необходимо было подготовить будущее военное вмешательство Антанты и замену австрийских и немецких контингентов на союзные войска.