Celiac disease (CD) is a common autoimmune disorder in which the patients are unable to digest gluten, which is present in foods made up of wheat, barley and rye. Whilst diagnosis happens late in 80% of the cases, avoidance of such foods appears to be the common solution. Alternative management strategies are required for the patients and their families since CD is also genetically carried over. Probiotic therapeutics and the consumption of appropriate enzymes, such as prolyloligopeptidases (POPs), from gut-friendly bacteria could reduce the disease burden and provide a better lifestyle for CD patients. We have examined around 5000 gut bacterial genomes and identified nearly 4000 non-redundant putative POPs. A select set of 10 gut bacterial POP sequences were subject to three-dimensional modelling, ligand docking and molecular dynamics simulations where stable interactions were observed between the POPs and gluten peptides. Our study provides sequence and structural analysis of potential POP enzymes in gut bacterial genomes, which form a strong basis to offer probiotic solutions to CD patients. In particular, these enzymes could be lead future therapeutics for this disease.