Complex organic molecules (COMs) are observed at all stages of star formation: in dark clouds, in protostellar envelopes, outflows and disks, and in planet-forming disks around pre-main sequence stars. They have been implicated in the origins of life on Earth, and are potential seeds of abiogenesis on other planets. They are also potential probes of a range of properties of the astrophysical environments they reside in. Most COMs are proposed to form on the surfaces of interstellar dust grains, through different kinds of ice chemistry. A broad and deep understanding of relevant ice chemical reactions is key to realize the potential of COMs as molecular probes, and to predict the chemical environment within which planets, comets, and asteroids assemble. In this talk I will introduce astrochemical observations of COMs during star and planet formation, highlighting several surprising discoveries. I will then present the different laboratory experiments that have been developed to address these unexpected COM observations, and the constraints they have provided on the origins of astrochemical complexity. I will also discuss some outstanding astrochemical mysteries and the laboratory data that will be needed to resolve them.