Polyelectrolytes continue to find wide interest and application in science and engineering, including areas such as water purification, drug delivery, and multilayer thin films. We have been interested in the dynamics of small molecules in a variety of polyelectrolyte (PE) environments; in this paper, we report simulations and analysis of the small dye molecule rhodamine B (RB) in several very simple polyelectrolyte solutions. Translational diffusion of the RB zwitterion has been measured in fully atomistic, 2 μs long molecular dynamics simulations in four different polyelectrolyte solutions. Two solutions contain the common polyanion sodium poly(styrene sulfonate) (PSS), one with a 30-mer chain and the other with 10 trimers. The other two solutions contain the common polycation poly(allyldimethylammonium) chloride (PDDA), one with two 15-mers and the other with 10 trimers. RB diffusion was also simulated in several polymer-free solutions to verify its known experimental value for the translational diffusion coefficient, DRB, of 4.7 × 10-6 cm2/s at 300 K. RB diffusion was slowed in all four simulated PE solutions, but to varying degrees. DRB values of 3.07 × 10-6 and 3.22 × 10-6 cm2/s were found in PSS 30-mer and PSS trimer solutions, respectively, whereas PDDA 15-mer and trimer solutions yielded values of 2.19 × 10-6 and 3.34 × 10-6 cm2/s. Significant associations between RB and the PEs were analyzed and interpreted via a two-state diffusion model (bound and free diffusion) that describes the data well. Crowder size effects and anomalous diffusion were also analyzed. Finally, RB translation along the polyelectrolytes during association was characterized.