An integrative electroanalytical method was developed for detecting Cd2+ and Pb2+ ions in aqueous solutions. Polysulfide/graphene (RGO-S) nanocomposites were prepared and their performance as electrochemical sensors for Cd2+ and Pb2+ was evaluated. The RGO-S nanocomposite was carefully characterized by scanning electron microscopy with energy-dispersive X-ray spectrometry, transmission electron microscopy, and X-ray photoelectron spectroscopy. The as-prepared RGO-S was incorporated into a pyrolytic graphite electrode (RGO-S/PGE) and used for detecting trace amount of Cd2+ and Pb2+ by differential pulse anodic stripping voltammetry. Under optimal conditions, the stripping peak current of RGO-S/PGE varies linearly with heavy metal ion concentration in the ranges 2.0-300 mu g L-1 for Cd2+ and 1.0-300 mu g L-1 for Pb2+. The limits of detection for Cd2+ and Pb2+ were estimated to be about 0.67 mu g L-1 and 0.17 mu g L-1, respectively. The prepared electrochemical heavy-metal-detecting electrode provides good repeatability and reproducibility with high sensitivity, making it a suitable candidate for monitoring Cd2+ and Pb2+ concentrations in aqueous environmental samples.