Khvostov was born in a noble family of land proprietors. After finishing the Imperial Alexander Lyceum in Tsarskoye Selo, he became a student in Law. In 1898 he married Ekaterina Popova, the daughter of Alexander Popov (1835-1914), a senator. In 1904 he became vice governor of Minsk and later that year was appointed in Tula. In 1906 Khvostov became Vice Governor and then Governor of Nizhny Novgorod. When Pyotr Stolypin was murdered Grigori Rasputin paid him a visit in order of the Tsar "to look in his soul", but came to the conclusion he was too young to be appointed as minister. Also Count Kokovtsov protested.
In 1912 he was elected to the Fourth Imperial State Duma as a member and president of the Russian Assembly, one of the right wing parties. He was Minister of the Interior from September 26, 1915 (Old Style) to March 3, 1916. His uncle Aleksandr Khvostov was opposed to the appointment of his nephew.
The Russian Minister of the Interior, A.N. Chvostov, has recently declared himself in favor of inaugurating a fight against the "yellow press", which has grown considerably during recent years. Not long ago, some of these newspapers were involved in "society scandals", their part in them being exposed by rather sensational trials. Mr. Chvostov's Ministry has under consideration a plan for exiling from Petrograd the journalists who were connected with the newspapers involved in the scandals.
After Khvostov came into office he began to intrigue against his colleagues, against the Prime Minister himself in order to get his place, and finally against his benefactor Rasputin. Khvostov and Iliodor concocted a plan to kill Rasputin. Khvostov had come to the conclusion that Rasputin was a German spy or agent. Evidence that Rasputin actually worked for the Germans is flimsy at best. In his efforts to plot against Rasputin (and not becoming Prime Minister) Khvostov had to resign. After Boris Stürmer, his uncle Aleksandr Khvostov, became his successor.
Khvostov was arrested and imprisoned in the Peter and Paul Fortress by the Russian Provisional Government during the February Revolution of 1917. In 1918, less than a year after the Bolsheviks seized power he was executed by firing squad in Petrovsky Park, Moscow.