As other answerers have said, the idiomatic use of "walk back" describes a backing off or distancing of oneself or one's organization from a statement that one (or it) has made on one's (or its) behalf that has drawn criticism and (often) widespread disapproval. It seems to be especially heavily used in political discussions and arguments.
Merriam-Webster Online doesn't offer a definition for "walk back" in this idiomatic sense, but it does have this entry for the phrase:
walk back intransitive verb : to ease back the fall of a hoisting-tackle while keeping it in hand
It's not impossible that someone familiar with this usage involving the controlled descent of a hoisting tackle might have applied it to a tactical revision of a political position, but most politicians and those who cover them are unlikely to find much resonance in the image of a pulley under hand control. Also, the political sense of "walk back" uses the verb transitively, not intransitively.
Two bits of evidence suggest that the idiomatic usage emerged fairly recently. First, Grant Barrett, The Oxford Dictionary of American Political Slang (2004), which is dedicated to precisely the area of U.S. English where the phrase seems to have arisen, shows no awareness of its existence.
Second, a series of Google Books searches for particular phrases that incorporate "walk back" in the relevant sense go back no farther than 2013. For example, a search for the phrase "walk back his earlier" finds matches for the longer phrases "walk back his earlier thesis" (2013), "walk back his earlier use" (2014), "walk back his earlier statement" (2014) [relevant text not shown in snippet window], and "walk back his earlier assertion" (2015).
The earliest match for "walk back [one's] X" that I found in a series of Google Books searches may not be related to the idiomatic sense that Yoichi Oishi asks about. From Norman Ford, Good Night: The Easy and Natural Way to Sleep the Whole Night Through (1983) [combined snippets]:
You can reschedule your bedtime for any hour you choose. But you should not try to "walk back" your bedtime in increments greater than three hours daily. This usually means you must take seven days off from work to complete the process.
If you are able to successfully overcome NS by changing your sleep hours, you might consider experimenting with Technique 7 to "walk back" your body temperature rhythm to a more natural time.
Here "walk back" refers to a systematic, calibrated, interval-based shift over a period of days, figuratively resembling a series of even footsteps that take a person from an undesirable position back to a comfortable and effective one. This has some similarities to the recent political idiom, but it differs in one crucial way: the political "walk back" consistently involves an attempt to recalibrate a message based on unexpected problems with the previous message; thus it is essentially reactionary—a reaction to a reaction. In contrast, Ford's bedtime "walk back" is the product of proactive—not reactive—strategic planning.
The earliest instance of the political idiom that I could find is from Kenneth Timmerman, Shadow Warriors: The Untold Story of Traitors, Saboteurs, and the Party of Surrender (2007):
There was always a dead period between the time you [a reporter] finished a piece and when it came out, and that was when bad things happened. Sources went south. Documents leaked. Government officials panicked and started calling editors, furiously trying to walk back their indiscretions. But when he saw the title to Dana Priest's latest story, “Secret World of U.S. Interrogation,” he feared the worst. He had been scooped.
Other somewhat early instances appear in The Civil Liberties Legacy of Harry S. Truman (2012):
Truman's suggestion to the contrary stuck in the newspapermen's craw and gave ammunition to those who argued he was acting unreasonably. Indeed, Truman's press secretary, Joseph Short, later walked back the president's claim and granted that if the correspondents received news from official channels they could feel safe in running it.And yet the irritation lingered.
and in Carnes Lord, Proconsuls: Delegated Political-Military Leadership from Rome to America Today (2012):
It seems clear that Bremer arrived in Baghdad determined to walk back the administration's established policy concerning an early transition to Iraqi sovereignty. This entailed, however, an American occupation of Iraq lasting — so Bremer seems to have expected — many years, along the lines of the postwar occupations of Germany and Japan.
The image that "walk back" originally intended to invoke is a matter for speculation, but in current usage it refers to something like an orderly tactical withdrawal from a previously stated view, rather than to a headlong retreat amounting to a rout. The phrase does seem represent a greater distancing than is implied by the idiomatic phrase "step back from."
The earliest Google Books match I could find for "walk back" in its now-common idiomatic sense is in Timmerman's book from 2007—but the expression seems to have penetrated popular culture in the United States only in the pas five years.