In response to white settlers' demands for tribal lands in the southeast, Congress passed the Indian Removal Act in 1830. The “Five Tribes”—Cherokees, Choctaws, Chickasaws, Muscogees (Creeks), and Seminoles—were then forced to Indian Territory (now Oklahoma). Natives had access to a vast array of fruits, vegetables, and game meats, and until the Civil War, their health problems appeared to be maladies such as wounds, parasites, contagious diseases, and illnesses associated with unsanitary conditions. Around the mid-1860s, natives' diets began changing in two ways: either they included an overabundance of wheat flour, sugar, salt, and lard that resulted in diet-related ailments such as diabetes, obesity, and tooth decay; or the amount of food was inadequate, and natives suffered from malnutrition. Using testimonies of early explorers and elderly residents of 1930s Oklahoma who recalled their days in the Territory, this essay explores the sustenance of the Five Tribes and considers how changing from a diet of fresh flora and fauna to calorie-dense, fatty, and carbohydrate-laden meals may have contributed to their declining health.