A novel video coding approach that performs adaptive rate-distortion optimization guided by perceptual hints is proposed in this paper. The key idea is to adoptively adjust the Lagrange multipliers of the RDO coder control module based on visual attention analysis. The observation is that human vision is sensitive to movement of well structured objects while tolerates large distortion in moving areas with random structure (texture-wise and motion-wise). The proposed algorithm analyzes permissible perceptual distortions and, accordingly, assigns larger Lagrange multipliers to regions that are perceptually less sensitive to distortion so that rate-reduction is weighted more than distortion reduction in these regions. Experiments show that this scheme achieves bit-rate saving of 5-7% with virtually same perceptual quality and is very promising for practical systems.