Enfant, Starostin était fragile, maladif et plutôt mis à l’écart. Mais l’enfant ne se satisfaisait pas de sa condition, il était ambitieux. C’est ainsi qu’avec le temps, il vient au pentathlon moderne et rêve de compétition. Il commence un travail sérieux et laborieux lorsqu’il mesure ses dispositions pour la course à pied.

Chez les juniors, il est devenu le meilleur du vaste pays et bientôt le meilleur mondial. C’est logiquement qu’à Moscou 1980, il monte sur la première marche du podium individuel, devenant le premier soviétique champion olympique de pentathlon. Dans la foulée il remporte également le titre par équipe.

Privé des Jeux de Los Angeles 1984 en raison du boycott soviétique, il va manquer les Jeux de Séoul 1988 car deux ans auparavant, il a été contrôlé positif à un produit interdit. Dans le cas de Starostin, il s’agissait d’hydroxybutyrate de sodium. Les médecins lui avaient alors conseillé ce produit afin de réduire la nervosité et soulager le stress lors des épreuves de tir sportif au pistolet. Lors de ce Championnat du monde 1986, 12 athlètes furent donc suspendus pour avoir utilisé le même produit.

Il fait son retour aux Jeux à Barcelone 1992 et douze ans après son sacre moscovite et prend la deuxième place de l’épreuve individuelle.

Après cela, Anatoly Starostin a été invité à diriger l’équipe nationale féminine russe du pentathlon moderne. Sous sa direction, l’équipe a remporté des médailles aux championnats d’Europe et du monde. C’est alors que le pentathlon moderne féminin devient à son tour discipline olympique en remplacement de la compétition masculine par équipe.