This paper describes a new kind of zeolite-modified electrodes (ZMEs) based on the physical immobilization of zeolite particles onto the surface of paraffin-impregnated graphite electrodes (PIGEs). Their electrochemical behavior was first evaluated by ion-exchange voltammetry using methylviologen as a model redox probe, indicating better performance in comparison to the corresponding zeolite-modified carbon paste electrodes. The zeolite-modified-PIGEs were then applied to the study of lead(II)-loaded zeolites to monitor their reaction with sulfide ions at various sulfidation levels. Both Pb(II) ions and PbS nanoparticles gave rise to well-defined voltammetric signals, but peak currents due to the more mobile Pb(II) ions were much higher than those recorded for PbS nanoparticles. This is due to the fact that Pb(II) ions underwent ion exchange for the electrolyte cation prior to the electron transfer whereas the PbS nanoparticles are immobilized in the microporous structure of the zeolite particles and thus less available for the redox reactions. Nevertheless, these signals were useful to discriminate between the various sulfidation levels, as ascertained by additional X-ray photoelectron spectroscopy measurements.