Biological tissues are rarely transparent, presenting major challenges for deep tissue optical microscopy. The achievable imaging depth is fundamentally limited by wavefront distortions caused by aberration and random scattering. Here, we report an iterative wavefront compensation technique that takes advantage of the nonlinearity of multiphoton signals to determine and compensate for these distortions and to focus light inside deep tissues. Different from conventional adaptive optics methods, this technique can rapidly measure highly complicated wavefront distortions encountered in deep tissue imaging and provide compensations for not only aberration but random scattering. The technique is tested with a variety of highly heterogeneous biological samples including mouse brain tissue, skull, and lymph nodes. We show that high quality three-dimensional imaging can be realized at depths beyond the reach of conventional multiphoton microscopy and adaptive optics methods, albeit over restricted distances for a given correction. Moreover, the required laser excitation power can be greatly reduced in deep tissues, deviating from the power requirement of ballistic light excitation and thus significantly reducing photo damage to the biological tissue.