Его рывок к вершине властного Эвереста начался в 1991 году, когда он был командующим Воздушно-десантными войсками СССР и принимал в Тульской воздушно-десантной дивизии Бориса Ельцина. Опальный деятель к тому времени вышел из КПСС, министр обороны Дмитрий Язов и его зам Владислав Ачалов запретили Грачёву устраивать для Ельцина тёплый приём, но тот их ослушался. В итоге после обеда со спиртным Грачёв с «приятным, умным, самостоятельным» Ельциным расстались друзьями.
Дружба вскоре перешла в «братство», причём довольно экзотическим способом, который позволяет предположить, что Ельцин в детстве увлекался книжками про американских индейцев, и некоторые моменты из их жизни навсегда запали ему глубоко в душу. Уже после событий августа 1991 года Ельцин, Грачёв и ещё несколько соратников пошли в лес, разложили выпить-закусить на валявшейся там покрышке от трактора «Беларусь» и по инициативе Ельцина поклялись друг другу в верности. «Борис Николаевич сам предложил: «Давайте брататься. Я вас в жизни никого не кину, и давайте клясться на крови». Взяли нож, порезали друг другу руки, лизали кровь... Сели и на крови поклялись по его инициативе. А он нас потом всех кинул. Неожиданно».
Ну что ж, как поётся в известной песне, «настоящему индейцу завсегда везде ништяк». Что с побратимами, что без них.
Дружбы с Грачёвым из-за его должности добивался не только Ельцин, но и законные власти страны, однако он их проигнорировал. А дело было так. Летом 1991 года глава Минобороны Язов передал Грачёву приглашение явиться на Лубянку для знакомства с Владимиром Крючковым, возглавлявшим КГБ. Тот рассказал Грачёву о «непонятной обстановке» в стране, о «некстати заболевшем» Михаиле Горбачёве, о начинающемся «брожении в народе». Намекнул, что возможна ситуация, когда потребуется поддержка армии. Затем велел Грачёву и ещё некоторым отправиться на подмосковную дачу и составить возможный план по переходу власти от Горбачёва к Политбюро. Те, впрочем, оказались никудышными стратегами: за трое суток так ничего и не придумали. «Единственно, я настоял, что роль ВДВ должна была заключаться в том, чтобы при возможности войти в Москву и взять под охрану основные здания, чтобы не разбили, как в 1917 году», – вспоминает Грачёв.
16 августа 1991 года замминистра обороны Ачалов приказал Грачёву подготовить две дивизии для ввода в Москву. Вскоре последовал и приказ о вводе. По телевизору в это время шло «Лебединое озеро». Намеченные объекты были быстро взяты под охрану. Об этом тут же прознал «побратим» Ельцин и позвонил Грачёву.