In late 1831, thirteen thousand Choctaws began the long journey west to a land and climate totally different from what they knew. "Marshaled by guards, hustled by agents, harried by contractors, they were being herded on the way to an unknown and unwelcome destination like a flock of sick sheep." They went on ox wagons, on horses, on foot, then to be ferried across the Mississippi River. The army was supposed to organize their trek, but it turned over its job to private contractors who charged the government as much as possible, gave the Indians as little as possible. Everything was disorganized. Food disappeared. Hunger came. Van Every again:

The long somber columns of groaning ox wagons, driven herds and straggling crowds on foot inched on westward through swamps and forests, across rivers and over hills, in their crawling struggle from the lush lowlands of the Gulf to the arid plains of the west. In a kind of death spasm one of the last vestiges of the original Indian world was being dismembered and its collapsing remnants jammed bodily into an alien new world.

The first winter migration was one of the coldest on record, and people began to die of pneumonia. In the summer, a major cholera epidemic hit Mississippi, and Choctaws died by the hundreds. The seven thousand Choctaws left behind now refused to go, choosing subjugation over death. Many of their descendants still live in Mississippi.

As for the Cherokees, they faced a set of laws passed by Georgia: their lands were taken, their government abolished, all meetings prohibited. Cherokees advising others not to migrate were to be imprisoned. Cherokees could not testify in court against any white. Cherokees could not dig for the gold recently discovered on their land. A delegation of them, protesting to the federal government, received this reply from Jackson's new Secretary of War, Eaton: "If you will go to the setting sun there you will be happy; there you can remain in peace and quietness; so long as the waters run and the oaks grow that country shall be guaranteed to you and no white man shall be permitted to settle near you."

The Cherokee nation addressed a memorial to the nation, a public plea for justice. They reviewed their history:

After the peace of 1783, the Cherokees were an independent people, absolutely so, as much as any people on earth. They had been allies to Great Britain… The United States never subjugated the Cherokees; on the contrary, our fathers remained in possession of their country and with arms in their hands… In 1791, the treaty of Holston was made… The Cherokees acknowledged themselves to be under the protection of the United States, and of no other sovereign… A cession of land was also made to the United States. On the other hand, the United States… stipulated that white men should not hunt on these lands, not even enter the country, without, a passport; and gave a solemn guarantee of all Cherokee lands not ceded.…

They discussed removal:

We are aware that some persons suppose it will be for our advantage to remove beyond the Mississippi. We think otherwise. Our people universally think otherwise.… We wish to remain on the land of our fathers. We have a perfect and original right to remain without interruption or molestation. The treaties with us, and laws of the United States made in pursuance of treaties, guarantee our residence and our privileges, and secure us against intruders- Our only request is, that these treaties may be fulfilled, and these laws executed…

Now they went beyond history, beyond law:

We entreat those to whom the foregoing paragraphs are addressed, to remember the great law of love. "Do to others as ye would that others should do to you."… We pray them to remember that, for the sake of principle, their forefathers were compelled to leave, therefore driven from the old world, and that the winds of persecution wafted them over the great waters and landed them on the shores of the new world, when the Indian was the sole lord and proprietor of these extensive domains-Let them remember in what way they were received by the savage of America, when power was in his hand, and his ferocity could not be restrained by any human arm. We urge them to hear in mind, that those who would not ask of them a cup of cold water, and a spot of earth… are the descendants of these, whose origin, as inhabitants of North America, history and tradition are alike insufficient to reveal. Let them bring to remembrance all these facts, and they cannot, and we are sure, they will not fail to remember, and sympathize with us in these our trials and sufferings.

Jackson 's response to this, in his second Annual Message to Congress 111 December 1830, was to point to the fact that the Choctaws and Chickasaws had already agreed to removal, and that "a speedy removal" of the rest would offer many advantages to everyone. For whites it "will place a dense and civilized population in large tracts of country now occupied by a few savage hunters." For Indians, it will "perhaps cause them, gradually, under the protection of the Government and through the influence of good counsels, to cast off their savage habits and become an interesting, civilized, and Christian community."

He reiterated a familiar theme. "Toward the aborigines of the country no one can indulge a more friendly feeling than myself…" However: "The waves of population and civilization are rolling to the westward, and we now propose to acquire the countries occupied by the red men of the South and West by a fair exchange.…"

Georgia passed a law making it a crime for a white person to stay in Indian territory without taking an oath to the state of Georgia. When the white missionaries in the Cherokee territory declared their sympathies openly for the Cherokees to stay, Georgia militia entered the territory in the spring of 1831 and arrested three of the missionaries, including Samuel Worcester. They were released when they claimed protection as federal employees (Worcester was a federal postmaster). Immediately the Jackson administration took away Worcester 's job, and the militia moved in again that summer, arresting ten missionaries as well as the white printer of the Cherokee Phoenix. They were beaten, chained, and forced to march 35 miles a day to the county jail. A jury tried them, found them guilty. Nine were released when they agreed to swear allegiance to Georgia 's laws, but Samuel Worcester and Elizur Butler, who refused to grant legitimacy to the laws repressing the Cherokees, were sentenced to four years at hard labor.

This was appealed to the Supreme Court, and in Worcester v. Georgia, John Marshall, for the majority, declared that the Georgia law on which Worcester was jailed violated the treaty with the Cherokees, which by the Constitution was binding on the states. He ordered Worcester freed. Georgia ignored him, and President Jackson refused to enforce the court order.

Georgia now put Cherokee land on sale and moved militia in to crush any sign of Cherokee resistance. The Cherokees followed a policy of nonviolence, though their property was being taken, their homes were being burned, their schools were closed, their women mistreated, and liquor was being sold in their churches to render them even more helpless.

The same year Jackson was declaring states' rights for Georgia on the Cherokee question in 1832, he was attacking South Carolina 's right to nullify a federal tariff. His easy reelection in 1832 (687,000 to 530,000 for his opponent Henry Clay) suggested that his anti-Indian policies were in keeping with popular sentiment, at least among those white males who could vote (perhaps 2 million of the total population of 13 million). Jackson now moved to speed up Indian removal. Most of the Choctaws and some of the Cherokees were gone, but there were still 22,00 °Creeks in Alabama, 18,00 °Cherokees in Georgia, and 5,000 Seminoles in Florida.