Energy-dispersive X-ray fluorescence (ED-XRF) spectroscopy with data treatment via chemometric tools was explored as an analytical protocol to discriminate between authentic and counterfeit revenue stamps. Untreated samples were directly analyzed, and the discrimination was based on the characterization of constituent elements present in the inks and paper. Authentic samples and samples that were suspected of being counterfeit were analyzed at three different areas on their surfaces: the ink-printed area, the non-printed area, and the holographic area. Principal component analysis (PCA) was applied to the data to discriminate between authentic and counterfeit revenue stamps. Major differences in the elemental composition were noted (according to chemometrics and t-test, p < 0.05), and ED-XRF spectroscopy plus PCA protocol is proposed for use by non-specialist operators to screen for counterfeit stamps.