Many low-income consumers face a limited budget for food purchases. The United States Department of Agriculture developed the Thrifty Food Plan to address this problem of consuming a healthy diet given a budget constraint. This dietary optimization program uses common food choices to build a suitable diet. In this article, the United States Department of Agriculture data sets are used to test the feasibility of consuming a Paleolithic diet given a limited budget. The Paleolithic diet is described as the diet that humans are genetically adapted to, containing only the preagricultural food groups of meat, seafood, fruits, vegetables, and nuts. Constraints were applied to the diet optimization model to restrict grains, dairy, and certain other food categories. Constraints were also applied for macronutrients, micronutrients, and long-chain polyunsaturated fatty acids. The results show that it is possible to consume a Paleolithic diet given the constraints. However, the diet does fall short of meeting the daily recommended intakes for certain micronutrients. A 9.3% increase in income is needed to consume a Paleolithic diet that meets all daily recommended intakes except for calcium.