It does not exactly match your description, but you may be thinking of "Thus We Frustrate Charlemagne", a short story by R. A. Lafferty, which was the answer to this old question and (unaccepted) to this one; first published in Galaxy Magazine, February 1967, available at the Internet Archive. Does any of these covers look familiar?
No protagonist travels to the past. Rather, a committee of scientists sits in their Institute and has their AI computing machine send an Avatar to the past to effect the desired changes, which they hope to observe in the present:
"We have perfect test conditions," the machine Epikt said as though calling them to order. "We set out basic texts, and we take careful note of the world as it is. If the world changes, then the texts should change here before our eyes. For our test pilot, we have taken that portion of our own middle-sized city that can be viewed from this fine vantage point. If the world in its past-present continuity is changed by our meddling, then the face of our city will also change instantly as we watch it.
"We have assembled here the finest minds and judgments in the world: eight humans and one Ktistec machine, myself. Remember that there are nine of us. It might be important."
[. . . .]
From his depths, Epiktistes the Ktistec machine sent out an Avatar, partly of mechanical and partly of ghostly construction. Along about sundown on the road from Pamplona to Roncesvalles, on August 14 of the year 778, the traitor Gano was taken up from the road and hanged on a carob tree, the only one in those groves of oak and beech. And all things thereafter were changed.
But of course the scientists were not aware of the changes:
"Did it work, Epikt? Is it done?" Louis Lobachevski demanded. "I can't see a change in anything."
"The Avatar is back and reports his mission accomplished," Epikt stated. "I can't see any change in anything either."
"Let's look at the evidence," Gregory said.
The thirteen of them, the ten humans and the Ktistec, Chresmoeidec and Proaisthematic machines, turned to the evidence, and with mounting disappointment.
[. . . .]
"No, there is not one word of the text changed," Gregory grumbled. "History followed its same course. How did our experiment fail? We tried, by a device that seems a little cloudy now, to shorten the gestation period for the new birth. It would not be shortened."
"The town is in no way changed," said Aloysius Shiplap. "It is still a fine large town with two dozen imposing towers of limestone and midland marble. It is a vital metropolis, and we all love it, but it is now as it was before."
After a second try they are stone age people, not lobsters:
"Did it work, Epikt? Is it done?" Aloysius asked.
"Let's look at the evidence," said Gregory.
The four of them, the three humans and the ghost Epikt, who was a kachenko mask with a speaking tube, turned to the evidence with mounting disappointment.
"There is still the stick and the five notches in it," said Gregory. "It was our test stick. Nothing in the world is changed."
"The arts remain as they were," said Aloysius. "Our picture here on the stone which we have worked for so many seasons is the same as it was. We have painted the bears black, the buffalos red and the people blue. When we find a way to make another color, we can represent birds also. I had hoped that our experiment might give us that other color. I had even dreamed that it might appear in the picture on the rock before our very eyes."
"There's still rump of skunk to eat and nothing else," said Valery. "I had hoped that our experiment would have changed it to haunch of deer."
On the third try they undo the changes and restore the world to its original state,