[1] His father was a grandson of Lieutenant-General Count Johann Ludwig von Wallmoden-Gimborn, an illegitimate son of King George II of Great Britain by his German born mistress, Countess Amalie Sophie Marianne von Wallmoden-Gimborn, created Countess of Yarmouth in 1740.

From 1876 he served as Hauptmann (captain) of the Baden District, Austria and from 1882 as an official of the state governments in the Cisleithanian crown lands of Bukovina and Carinthia as well as in the Austrian Ministry of the Interior.

After Minister-President Alfred III, Prince of Windisch-Grätz had resigned over the language conflict with the Young Czech Party in the Kingdom of Bohemia, Kielmansegg, a friend and a confidant of Emperor Francis Joseph I of Austria, was appointed Minister of the Interior and Cisleithanian Prime Minister on 18 June 1895, though only as an acting officeholder until the implementation of the Badeni government on 29 September.

In August 1892 Countess Anastasia von Kielmannsegg allegedly took part in sword duel with Princess Pauline von Metternich over a floral arrangement at the Vienna Musical and Theater Exposition, which was later denied by the Princess as a "ridiculous invention by Italian journalists".

A born North German he was, with the exception of Chancellor Count Friedrich Ferdinand von Beust, the only Protestant minister of Austria up to this date.