In this Letter, we investigate the feasibility of focusing relativistic laser pulses toward diffraction limit by near-critical density plasma lenses. A theoretical model is developed to estimate the focal length of the plasma lens. Particle-in-cell simulations with various pulse parameters, such as pulse duration, beam waist, and intensity, are performed to show the robustness of plasma lenses. The results prove that the near-critical density plasma lenses can be deployed to obtain higher laser peak intensities with sub-wavelength focal spots in experiments.