The treatment of Celiac disease consists in a strict lifelong gluten-free (GF) diet. As the ingestion of small amounts can have damaging complications, there has been an ongoing discussion regarding the safe threshold for dietary residual gluten. The aim was to analyze the evolution of gluten content in cereal-based GF foodstuffs (n = 3141) from 1998 to 2016 measured by the enzyme-linked immunosorbent assay (ELISA) technique. Eight categories were defined: flours, breakfast cereals/bars, bakery, pasta, breads, dough, snacks, and yeasts, and these were divided into GF labeled-foods (GF-L) or reportedly GF foodstuffs, but not certified (GF-NC). Gluten-detection was decreased over time in line with the evolving European regulations about food information and gluten content claims. This decline started sooner in GF-L products than in GF-NC. As a whole, gluten was detected in 371 samples, with breakfast cereals/bars being the most contaminated group. Snacks and yeasts changed from being high gluten-detected samples to being totally GF over the years. The downside is that, of contaminated samples, those in the low levels of gluten detection range have decreased while flour samples containing over 100 mg/kg gluten have risen in the 2013–2016 period. Obtained data confirm that GF cereal-based foods are becoming safer but gluten control must be maintained.