Celiac disease is caused by an uncontrolled immune response to gluten, a heterogeneous mixture of wheat storage proteins, including the α-gliadins. It has been shown that α-gliadins harbor several major epitopes involved in the disease pathogenesis. A major step towards elimination of gluten toxicity for celiac disease patients would thus be the elimination of such epitopes from α-gliadins. We have analyzed over 3,000 expressed α-gliadin sequences from 11 bread wheat cultivars to determine whether they encode for peptides potentially involved in celiac disease. All identified epitope variants were synthesized as peptides and tested for binding to the disease-associated HLA-DQ2 and HLA-DQ8 molecules and for recognition by patient-derived α-gliadin specific T cell clones. Several specific naturally occurring amino acid substitutions were identified for each of the α-gliadin derived peptides involved in celiac disease that eliminate the antigenic properties of the epitope variants. Finally, we provide proof of principle at the peptide level that through the systematic introduction of such naturally occurring variations α-gliadins genes can be generated that no longer encode antigenic peptides. This forms a crucial step in the development of strategies to modify gluten genes in wheat so that it becomes safe for celiac disease patients. It also provides the information to design and introduce safe gluten genes in other cereals, which would exhibit improved quality while remaining safe for consumption by celiac disease patients.