Annual grain crops dominate agricultural landscapes and provide the majority of calories consumed by humanity. Perennial grain crops could potentially ameliorate the land degradation and off-site impacts associated with annual grain cropping. However, herbaceous perennial plants with constitutively high allocation to harvestable seeds are rare to absent in nature. Recent trade-off theory models suggest that rugged fitness landscapes may explain the absence of this form better than sink competition models. Artificial selection for both grain production and multiyear lifespan can lead to more rapid progress in the face of fitness and genetic trade-offs than natural selection but is likely to result in plant types that differ substantially from all current domestic crops. Perennial grain domestication is also likely to require the development of selection strategies that differ from published crop breeding methods, despite their success in improving long-domesticated crops; for this purpose, we have reviewed literature in the areas of population and evolutionary genetics, domestication, and molecular biology. Rapid domestication will likely require genes with large effect that are expected to exhibit strong pleiotropy and epistasis. Cryptic genetic variation will need to be deliberately exposed both to purge mildly deleterious alleles and to generate novel agronomic phenotypes. We predict that perennial grain domestication programs will benefit from population subdivision followed by selection for simple traits in each subpopulation, the evaluation of very large populations, high selection intensity, rapid cycling through generations, and heterosis. The latter may be particularly beneficial in the development of varieties with stable yield and tolerance to crowding.