Khoudekov naît à Moscou dans une famille de la petite noblesse du gouvernement de Riazan. Il étudie au lycée no 3 de Moscou, puis à la faculté de Moscou. Il entre ensuite dans l'armée, dont il sort en 1869 avec le grade de major. C'est en 1860 qu'il commence sa carrière littéraire. Il écrit plusieurs pièces de théâtre, des romans, une Histoire de la danse en quatre tomes, ainsi que plusieurs livrets de ballet.
Khoudekov loue la Gazette de Saint-Pétersbourg en 1869 et l'achète deux ans plus tard, le . Le premier numéro de la nouvelle formule paraît le . C'était auparavant un journal au tirage limité (six cents exemplaires) et il va lui donner une nouvelle impulsion. Désormais la gazette paraît quatre fois par semaine, jusqu'en 1875, puis cinq fois par semaine. Il s'entoure de collaborateurs compétents, si bien qu'elle paraît quotidiennement à partir de 1882, tandis que son contenu est augmenté, jusqu'à quatre fois. Il en est aussi le rédacteur en chef. Il est l'auteur du livret avec Marius Petipa du ballet, Roxana, la beauté du Monténégro, sur une musique de Léon Minkus (1878).
Il achète en 1870 un grand parc près du village d'Erlino dans le gouvernement de Riazan et en fait un arboretum et un territoire agricole, avec un parc paysager et des étangs, aménagé selon les principes les plus modernes de l'époque. Il reçoit pour cela une médaille d'or à l'exposition universelle de Paris. Il achète une villa à Sotchi en 1890 et en deux ans aménage un grand parc dans un terrain autrefois désolé. Il fait venir les plantes et les arbres les plus variés qui sont à la base du parc botanique actuel.
Il était l'époux de Nadejda Strakhova, sœur de la femme de lettres Lydia Avilova (1864-1943).
