Since the original work on Bose–Einstein condensation^1,2, the use of quantum degenerate gases of atoms has enabled the quantum emulation of important systems in condensed matter and nuclear physics, as well as the study of many-body states that have no analogue in other fields of physics³. Ultracold molecules in the micro- and nanokelvin regimes are expected to bring powerful capabilities to quantum emulation⁴ and quantum computing⁵, owing to their rich internal degrees of freedom compared to atoms, and to facilitate precision measurement and the study of quantum chemistry⁶. Quantum gases of ultracold atoms can be created using collision-based cooling schemes such as evaporative cooling, but thermalization and collisional cooling have not yet been realized for ultracold molecules. Other techniques, such as the use of supersonic jets and cryogenic buffer gases, have reached temperatures limited to above 10 millikelvin^7,8. Here we show cooling of NaLi molecules to micro- and nanokelvin temperatures through collisions with ultracold Na atoms, with both molecules and atoms prepared in their stretched hyperfine spin states. We find a lower bound on the ratio of elastic to inelastic molecule–atom collisions that is greater than 50—large enough to support sustained collisional cooling. By employing two stages of evaporation, we increase the phase-space density of the molecules by a factor of 20, achieving temperatures as low as 220 nanokelvin. The favourable collisional properties of the Na–NaLi system could enable the creation of deeply quantum degenerate dipolar molecules and raises the possibility of using stretched spin states in the cooling of other molecules.