In this work, the lateral mobility of polyelectrolyte multilayers was investigated by means of the fluorescence recovery after photobleaching (FRAP) technique, with special attention to the effect of relevant parameters during and after preparation. Different polyelectrolytes with respect to charge density, stiffness, and hydrophilicity were compared. From the experimental results emerged that the density of charged sites along the polymer is the most important parameter controlling the formation of polymer complexes. At higher charge density, more complexes are formed, and the diffusion coefficient decreases. It was observed that the intrinsic backbone stiffness reduces the interpenetration of polyelectrolyte layers and the formation of complexes promoting the lateral mobility. In addition, the lateral mobility increases with increasing ionic strength and with decreasing hydration shell of the added anion in the polyelectrolyte solution. The effect of heating or annealing in electrolyte solution after preparation was also investigated along with the embedding of the probing layer at controlled distances to the multilayer surface.