Vsevolozhsky ran the Imperial Theatres with a determination for excellence. In 1886, Vsevolozhsky initiated two major reforms for the St. Petersburg Imperial Theatres, namely the relocation of the Imperial Ballet and Opera from the Bolshoi Kamenny Theatre (deemed unsafe by 1886) to the Mariinsky Theatre, and the abolition of the post of First Imperial Ballet Composer, a post previously held by such composers as Léon Minkus and Cesare Pugni. Alexandre Benois and Roland John Wiley credit him with the revival of ballet as a serious art form in Russia.
Vsevolozhsky's family was from Ryurik, with the Smolensk princes included among his illustrious ancestors. He graduated from the University of St Petersburg before working in the Asian section of the Department of International Affairs, the Russian consulate in The Hague, and as an official in St Petersburg. Despite having no background in management, or indeed theatre, Vsevolozhsky developed a love for theatre and French culture in general during his assignment to the Russian consulate in Paris from 1876. After the ascension of Alexander III, he was appointed as Director of Imperial Theatres from 3 September 1881.
Though a relative unknown, Vsevolozhsky was a vigorous and ‘enchantingly kind’ figure with ‘astonishing insight’. Vsevolovsky was responsible for who brought about the very existence of such world-famous ballets as The Sleeping Beauty (Tchaikovsky/Petipa) and The Nutcracker (Tchaikovsky/Ivanov).
In 1889, he duly instructed the Imperial Balletmaster Marius Petipa to choreograph a full-length ballet to the story "The Sleeping Beauty" for a premiere at the Mariinsky Theatre. He successfully obtained the most famous Russian composer to write the score for it, one Pyotr Ilyich Tchaikovsky. Vsevolojskoy wrote the libretto himself; in his career, he had been both a playwright and an essayist and was also a talented artist capable of designing costumes for the theater. Because of his vision, The Sleeping Beauty ballet (1890) is said to have had the most expensive and elaborate scenery and costumes ever seen.
He was an industrious costume-sketcher, preparing at least 1,087 drawings for 25 or more productions including those for the original productions of The Sleeping Beauty (1890) and The Nutcracker (1892).
As a great admirer of Tchaikovsky's music, Vsevolozhsky was instrumental in bringing to the stage three of that composer's later operas, namely The Enchantress (1886), The Queen of Spades (1889 – with libretto after Pushkin by the composer's brother, Modeste Tchaikovsky), and Iolanta (1892 – also with libretto by Modeste Tchaikovsky). Iolanta (sometimes written as Iolanthe) was commissioned expressly by Vsevolozhsky as the first part of a two-act gala evening which would conclude with a ballet called The Nutcracker. This two-act ballet was intended to showcase the choreography of Imperial Ballet Master Marius Petipa but eventually was created by assistant balletmaster Lev Ivanov, due to Petipa's failing health. The premiere of Iolanta and The Nutcracker on December 6, 1892 was a mild success and prompted the famous composer to believe that it would enjoy some popularity for 'at least a couple of years.'
Among his sweeping administrative changes as Director was the formation of a committee to determine repertory, salary raises for artists and workers (some of which were increased as much as sevenfold) and a rise in authors' fees to 10% (from 2%). However some measures were unsuccessful, such as his prohibition of free ticket distribution, increase in orchestra size, and expansion on rights of production of theatre posters. Most widely contested was their cost; the reforms increased spending by 10 times that of his predecessor, Baron Kister, and attempts to raise ticket prices was 'universally condemned'.
Vsevolozhsky's artistic preferences were French, though it was his refined yet unpretentious personal manner that attracted Tchaikovsky to working with him. He was one of Tchaikovsky's most vehement supporters. This relationship, however, worked both ways; the demand for new music well overshadowed supply and it was this permanent pressure that drove Tchaikovsky back to ballet after the lukewarm reception of Swan Lake, as well as Vsevolozhsky's generous facilitation of his resumed efforts. The composer's diary suggests a close relationship between himself and the Director; he recounts rushing to the former's house for urgent creative meeting that included Marius Petipa and Alexandre Petrovich Frolov.
Vsevolozhsky similarly championed Marius Petipa, with whom he had a fruitful relationship culminating in productions of 'L'Ordre du roi', 'Les Ruses d'amour' and 'Sleeping Beauty' that echoed the French golden age of ballet. However, his main allegiance remained to the cause for which he had been appointed, namely championing Russian ballet. His critics, such as Skalkovsky, lamented the lack of foreign dancers, and only in exceptional cases did he waver in his commitment to Russian art, as Wiley attests. This also reflected the wishes of the Russian royal family; the Tsar had abolished the Italian imperial opera in favour of the Russian before his appointment. Vsevolozhsky was also expected to positively influence Russian literatures, social mores and the national consciousness. His views on the state monopoly on theatrical productions are unknown, though contemporary critics appreciated its role in maintaining highbrow, high quality performances (for example, as opposed to Opera in Paris).
In 1899 Vsevolozhsky become director of the Hermitage Museum until his death in 1909. He married Ekaterina Dmitrievna Volkonsky, grand daughter of Field Marshall Prince P.M. Volkonsky (1776–1852) who, under Tsar Alexander I, had participated in the battle of Austerlitz against Napoleon.