This work describes the fabrication of poly(4-styrenesulfonic acid)-doped polyaniline/graphene (PSS-doped PANI/graphene) nanocomposites and their use as sensing elements for hydrogen sulfide (H2S) detection. PSS with a weight-average molecular weight (Mw) of 1.96 × 10(6) was synthesized using low-temperature free-radical polymerization. The PSS was used as both a doping agent and a binding agent for the polymerization of aniline monomers in a biphasic system (water-chloroform) at -50 °C. The high Mw of PSS resulted in relatively large particle sizes and smooth surfaces of the PSS-doped PANI. These physical characteristics, in turn, resulted in low interparticle resistance and high conductivity. In addition, the PSS allowed homogeneous dispersion of reduced graphene sheets through electrostatic repulsion. The prepared PSS-doped PANI/graphene solutions showed good compatibility with flexible poly(ethylene terephthalate) (PET) substrates, making them suitable for flexible sensor electrodes. Changes in the charge-transport properties, such as protonation level, conjugation length, crystalline structure, and charge-transfer resistance, of the electrode materials were the main factors influencing the electrical and sensor performance of the PSS-doped PANI-based electrodes. PSS-doped PANI/graphene composites containing 30 wt% graphene showed the highest conductivity (168.4 S cm(-1)) and the lowest minimum detection level (MDL) for H2S gas (1 ppm). This result is consistent with the observed improvements in charge transport in the electrode materials via strong π-π stacking interactions between the PANI and the graphene sheets.