The phrase to vote with one’s feet means to express one’s disapproval or dissatisfaction by leaving the place where it is happening or leaving the organisation that is supporting it.

The authors of the texts in which are the earliest instances that I have found all attributed the metaphor to the Russian statesman and Marxist theoretician Vladimir Ilich Lenin (born Vladimir Ilich Ulyanov – 1870-1924)—I have, however, found no confirmation of this.

The earliest instance is from Freedom To-day, by the English socialist politician and author Margaret Isabel Cole (née Postgate – 1893-1980), published in The News & Advertiser (Todmorden, Yorkshire) of Friday 18^th May 1934:

I have just come back from seeing a performance of that delightful film of Rene Claire’s [sic], A Nous La Liberte¹”—which incidentally is a very good antidote, if anyone has been seeing too many Russian propagandist pictures. As most people know I imagine, the theme of this film is the story of two prisoners who escape, the one to become head of an enormous highly-mechanised gramophone factory and the other to work in that factory—and who finally discover that their new life is as like prison as their old, and, aided a little by circumstance, march away down the road in tramp-clothes, singing “a nous la liberte!” While in the factory which the former has abandoned the machines work unheeded and their former attendants play cards or fish on the river bank. A very charming and attractive vision, although for most people only a vision.
For, in fact, humanity, at least western humanity, has decided—“voting with its feet,” as Lenin used to say—that it does not prefer the tramp life, in the whole to the life which is enjoined upon it by machine production and all the engines of what we call civilisation.

¹ À nous la liberté (1931), directed by René Clair (René-Lucien Chomette – 1898-1981), French filmmaker and author

The second-earliest instance is from The Road to Caporetto, by the British socialist activist and military theorist Thomas Henry Wintringham (1898-1949), published in the Left Review (Writers’ International, British Section – London) of November 1935:

(text: Marxists Internet Archive)
From my bookshelf the title of a book looks down on me ironically “Farewell to Arms,” Ernest Hemingway² called it. I shall not quote it; that would take too long. But no summary could do justice to the chapter that I remember most clearly, the description of the panic-mutiny of a million men, after the defeat at Caporetto.
“We’re going home,” those men said. They had seen enough war; they were tired of it. They had seen through the lies of war “patriotism,” and through the fame of their own generals, incompetent fools unable to watch the flanks, letting their troops be butchered in their rest billets, letting their guns be taken from the rear. When an army ceases to believe in its commanders, it tries to go home. It “votes for peace”; that is the way Lenin described it. “But they never have had a chance to vote,” someone answered him. “They have voted with their feet—they’ve gone home,” Lenin said. The Italians now in Ethiopia will, inevitably, vote with their feet before this war ends. Their feet will take them to a new Caporetto and beyond.

² A Farewell to Arms (1929), by Ernest Miller Hemingway (1899-1961), American novelist, short-story writer and journalist

In 1939, The Evening News (Harrisburg, Pennsylvania) serialised the book published the following year under the title Stalin Czar of all the Russias, by the American journalist and author Eugene Lyons (1898-1985), who had spent six years in the Soviet Union as a correspondent of United Press International; in one of the chapters published in that newspaper on Monday 20^th November, the author used the phrase when writing about the Russian Revolution of 1917:

From the fronts, soldiers streamed into the capital. They were “voting with their feet,” as Lenin put it, by abandoning the war. Those who remained in the war area ceased to obey their officers, formed soldiers’ councils or Soviets, and fraternized with the enemy soldiers.

Another early instance is from the Dumfries and Galloway Standard and Advertiser (Dumfries, Scotland) of Wednesday 4^th August 1943—it is interesting that the orator picks up on the very idea expressed by Thomas Henry Wintringham:

Mr D. Lesslie, chairman of Dumfries Communist Party, addressed an interested crowd in High Street on Sunday night. The fall of Mussolini, he said, primarily the result of the terrific blows of the Eighth and Allied Armies, resulted from the fact that the Italian people were not behind the Fascist regime. The soldiers “voted with their feet” for peace, by leaving the battlefield to surrender.

The phrase seems to have been popular among Communists; another early occurrence is from the analysis of the collapse of Chiang Kai-shek’s regime in continental China, by a certain Pat McLaughlin, who had worked in China as a correspondent of International News Service—analysis published in The Abilene Reporter-News (Abilene, Texas) of Saturday 14^th February 1953:

“In September, 1946, No. 2 China Red, Chou En-lai, sneeringly told me that Gen. Marshall and the American government were doing everything possible to prevent the collapse of Chiang, but scornfully predicted that Chiang’s soldiers ‘would vote with their feet.’ As they did when they deserted by the millions.”