In 1864, he entered the chancellery of the minister of foreign affairs at St.Petersburg, and was soon afterwards attached to the Russian legation at Stuttgart, where he attracted the notice of Queen Olga of Württemberg.

During the Russo-Turkish War of 1877-78, he was a delegate of the Red Cross Society in charge of an ambulance train provided by Queen Olga of Württemberg.

In Denmark, he was brought much into contact with the imperial family, and, on the death of Prince Lobanov-Rostovsky in 1896, he was appointed by Tsar Nicholas II to be his minister of foreign affairs.

When Tsar Nicholas II inaugurated the Peace Conference at The Hague in 1899, Count Muravyov extricated his country from a situation of some embarrassment in China; but when, subsequently, Russian agents in Manchuria and Peking connived at the agitation which culminated in the Boxer Rebellion of 1900, relations between Muravyov and the tsar became strained.

Muravyov died suddenly on June 21, 1900, after a stormy interview with Sergei Witte and Aleksey Kuropatkin in which Witte laid considerable blame on Muravyov for the crisis in China (Muravyov had insisted on taking Port Arthur against Witte's advice); because there was a wound on his left temple when he died, there was a rumor that he had committed suicide, but "the official government announcement asserted that, after rising late, he had merely slipped in his study and grazed his temple on the sharp side of a bureau.