This is "The Game of Blood and Dust" (1975)1 by Roger Zelazny.
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.
Mark Olson found the text of the story; other content was just based on quotes from the story and ISFdb.