It has been roughly three decades since laser cooling techniques produced ultracold atoms1, 2, 3, leading to rapid advances in a wide array of fields. Laser cooling has not yet been extended to molecules because of their complex internal structure. However, this complexity makes molecules potentially useful for a wide range of applications4. For example, heteronuclear molecules possess permanent electric dipole moments that lead to long-range, tunable, anisotropic dipole–dipole interactions. The combination of the dipole–dipole interaction and the precise control over molecular degrees of freedom possible at ultracold temperatures makes ultracold molecules attractive candidates for use in quantum simulations of condensed-matter systems5 and in quantum computation6. Also, ultracold molecules could provide unique opportunities for studying chemical dynamics7, 8 and for tests of fundamental symmetries9, 10, 11. Here we experimentally demonstrate laser cooling of the polar molecule strontium monofluoride (SrF). Using an optical cycling scheme requiring only three lasers12, we have observed both Sisyphus and Doppler cooling forces that reduce the transverse temperature of a SrF molecular beam substantially, to a few millikelvin or less. At present, the only technique for producing ultracold molecules is to bind together ultracold alkali atoms through Feshbach resonance13 or photoassociation14. However, proposed applications for ultracold molecules require a variety of molecular energy-level structures (for example unpaired electronic spin5, 9, 11, 15, Omega doublets16 and so on). Our method provides an alternative route to ultracold molecules. In particular, it bridges the gap between ultracold (submillikelvin) temperatures and the ~1-K temperatures attainable with directly cooled molecules (for example with cryogenic buffer-gas cooling17 or decelerated supersonic beams18). Ultimately, our technique should allow the production of large samples of molecules at ultracold temperatures for species that are chemically distinct from bialkalis.