По легенде, В. И. Чапаев, узнав о назначении на пост командующего фронтом полковника Генштаба старой армии, направил к Каменеву своего представителя Якова Пугача, чтобы выяснить, что за человек возглавил фронт и, вероятно, нет ли угрозы контрреволюции. Посланец, возвратившись, отчитался (существуют разные варианты этого «отчета»): «Перво-наперво – усищи во-о-о! Глазищи – как у разбойника Чуркина. Собой детина што надо. Ручищи… во! Одно слово, старик правильный (Каменеву в действительности было 38 лет. – А. Г.). Как мигнет глазами, ажно мурашки по загривку пойдут. Не балуется. Денщиков и вообще бездельников около себя не держит. Сапоги сам чистит, как наш Василий Иваныч. Твердый и смелый в речах. Подручных держит в руках. Над планами они сидят до петухов. Баб в штабу не приметил. Старик «свой» и не зазнается: единым махом к нему в избу проскочил. Говорит, скажи привет доблестным красным войскам Пугачевской округи и Чапаеву. Сам, говорит, скоро приеду знакомиться, как только, мол, здесь вздохну. На прощеванье за руку взял».
В кампанию 1919 г. Каменев сыграл важную роль в победе над армиями адмирала А. В. Колчака на Восточном фронте. Однако в самый разгар операций в результате конфликта с главкомом И. И. Вацетисом был неожиданно снят с должности и вынужденно бездействовал несколько недель, хотя и пытался влиять на события на фронте. Вместо него фронт возглавил А. А. Самойло, присланный с севера России. Но из-за конфликта с РВС фронта и подчиненными Самойло на этом посту долго не продержался, а должность командующего вновь занял Каменев, заручившийся поддержкой В. И. Ленина.
По его собственному признанию, Каменев плохо ориентировался в политической обстановке, видевшейся ему «как в тумане». Важную роль в политическом становлении Каменева сыграл член РВС Восточного фронта С. И. Гусев. В июле 1919 г. в результате скандального «дела» Полевого штаба Реввоенсовета республики, ставшего проявлением политической борьбы группировок в большевистской верхушке, главком И. И. Вацетис был смещен и арестован вместе со своим ближайшим окружением. Новым главнокомандующим всеми вооруженными силами стал Каменев. Именно С. И. Гусев способствовал тому, что на Каменева обратил внимание большевистский лидер В. И. Ленин. В итоге Каменев оказался на посту главнокомандующего – высшей должности в Советской России, на которую мог рассчитывать беспартийный военспец. Ближайшим соратником Каменева в Гражданскую войну как на Восточном фронте, так и на посту главкома стал Павел Павлович Лебедев – бывший генерал и талантливый генштабист.