The adiabatic theory of strong-field ionization of molecules with internuclear motion included into consideration is developed. Two adiabatic regimes in terms of the electronic, nuclear, and laser field timescales are considered. In the first regime, field is the slowest; that is, its timescale is much larger than the electronic and nuclear timescales. The corresponding theory generalizes the adiabatic theory of strong-field ionization of atoms and molecules with frozen nuclei [Phys. Rev. A 86, 043417 (2012)] by treating the internuclear motion on equal footing with the electronic motion. In the second regime, the active electron is the fastest; that is, its timescale is much smaller than that of the nuclei and laser field. The corresponding theory naturally involves the Born-Oppenheimer approximation. The two versions of the adiabatic theory are validated by comparing their predictions with accurate numerical results obtained by solving the time-dependent Schrödinger equation (TDSE) for a model diatomic molecule with one electronic and one internuclear degree of freedom. The adiabatic results are shown to converge to the TDSE results uniformly with respect to the laser field amplitude both in tunneling and over-the-barrier ionization regimes. Two applications of the theory to the analysis of strong-field effects associated with the internuclear motion are discussed.