During the early presidency of Vladimir Putin he was tasked with conducting high level military negotiations that involved the United States, NATO, and China.

As the Chief of the General Staff he favored reorganizing the army into brigades and having the majority of troops be contract soldiers instead of conscripts.

But in 2008 he opposed the efforts of new Defense Minister Anatoly Serdyukov to implement major reforms in the Russian military command structure and their disagreements led to Baluyevsky stepping down.

[3] In the early postwar years his father was stationed in western Ukraine to fight the Ukrainian nationalist insurgency, which was when Baluyevsky was born.

[7] In 1993, during the War in Abkhazia, he became the chief of staff and the first deputy commander of the Group of Forces of the Transcaucasus,[1][6] working at its headquarters in Tbilisi, Georgia.

Russian military analyst Pavel Felgenhauer described his long career at there as "outstanding" and called him a "capable staff general.

"[8] He was serving in that position when the Kosovo War started in early 1999 and Russia was going to be excluded by the NATO countries from taking part in the peacekeeping mission there.

In May 1999 Baluyevsky ordered the Russian Airborne brigade of the Stabilization Force in Bosnia and Herzegovina to secretly prepare to enter Kosovo.

Under Secretary of Defense for Policy Douglas Feith to start negotiations on the reduction of nuclear warheads in the arsenals of both countries, and also to discuss the U.S. decision to withdraw from the Anti-Ballistic Missile Treaty.

[2][21] In 2005 he said that the existing Ground Forces structure of army, division, regiment, and battalion was outdated, designed to fight a World War II-style conflict.

[27] When the U.S. announced plans to set up a missile shield in Europe in early 2007, Baluyevsky stated that Russia could withdraw from the Intermediate-Range Nuclear Forces Treaty.

[28] On 19 January 2008, Baluyevsky warned that Russia was ready to use force, including pre-emptively and with nuclear weapons, to defend itself against the potential threats from "international terrorism or countries seeking global or regional hegemony.

When Anatoly Serdyukov was given that post and tried to implement radical military reforms, Baluyevsky opposed his efforts,[8][21] including the relocation of the Navy Headquarters from Moscow to Saint Petersburg and changes to the Ministry of Defense and the General Staff.

[7] His disagreement and open criticism of Serdyukov led to him being replaced on 3 June 2008 with General Nikolai Makarov, who was a supporter of the reforms.