This is "The Game of Blood and Dust" (1975)1 by Roger Zelazny, originally published in Galaxy.
It is about two characters, Blood and Dust, altering history through time travel. They have the power to go to any time.
Apparently, they fail to prevent Lincoln's death (emphasis mine):
Blood entered Chewy's Theater on the evening in 1865 when the disgruntled actor had taken a shot at the President of the United States.
Delicately altering the course of the bullet in midair, he made it reach its target.
However, they stop Nikita Khrushchev's death (emphasis mine):
Blood entered the century at a farther point and assured the failure of Leon Nozdrev, the man who had assassinated Nikita Khrushchev.
Credit to Adamant for finding this from another question, answered by Mark Olson.
Quotes from here; other content from ISFdb. The link to that text is dead; here it is live.