Decapping enzymes are required for the removal of the 5'-end (m7)GpppN cap of mRNAs to allow their decay in cells. While many cap-binding proteins recognize the cap structure via the stacking of the methylated guanosine ring between two aromatic residues, the precise mechanism of cap recognition by decapping enzymes has yet to be determined. In order to get insights into the interaction of decapping enzymes with the cap structure, we studied the vaccinia virus D10 decapping enzyme as a model to investigate the important features for substrate recognition by the enzyme. We demonstrate that a number of chemically modified purines can competitively inhibit the decapping reaction, highlighting the molecular features of the cap structure that are required for recognition by the enzyme, such as the nature of the moiety at positions 2 and 6 of the guanine base. A 3D structural model of the D10 protein was generated which suggests amino acids implicated in cap binding. Consequently, we expressed 17 mutant proteins with amino acid substitutions in the active site of D10 and found that eight are critical for the decapping activity. These data underscore the functional features involved in the non-canonical cap-recognition by the vaccinia virus D10 decapping enzyme.