Celiac disease represents a significant public health problem in large parts of the world. A major hurdle in the effective management of the disease by celiac sufferers is the sensitivity of the current available methods for assessing gluten contents in food. In response, we report a highly sensitive approach for gluten analysis using aptamers as specific receptors. Gliadins, a fraction of gluten proteins, are the main constituent responsible for triggering the disease. However, they are highly hydrophobic and large molecules, regarded as difficult targets for in vitro evolution of aptamers without nucleobase modification. We describe the successful selection of aptamers for these water insoluble prolamins that was achieved choosing the immunodominant apolar peptide from α2-gliadin as a target for selection. All aptamers evolved are able to bind the target in its native environment within the natural protein. The best nonprotein receptor is the basis for an electrochemical competitive enzyme-linked assay on magnetic particles, which allows the measurement of as low as 0.5 ppb of gliadin standard (0.5 ppm of gluten). Reference immunoassay for detecting the same target has a limit of detection of 3 ppm, 6 times less sensitive than this method. Importantly, it also displays high specificity, detecting the other three prolamins toxic for celiac patients and not showing cross-reactivity to nontoxic proteins such as maize, soya, and rice. These features make the proposed method a valuable tool for gluten detection in foods.