The past 40 years of astrochemistry has showed that unusual molecules readily form in extreme interstellar environments. One of these interesting settings is the material lost from stars in their final stages. Here gas-phase material is ejected from the hot stellar photosphere, often at high velocities, and rapidly cools to create molecules and dust grains under competing thermodynamic and kinetic conditions. Using a combined program of high-resolution laboratory spectroscopy and astronomical observations, we have been investigating the chemistry of stellar ejecta. Measurements of rotational spectra of small, metal-bearing molecules using millimeter-wave and Fourier transform microwave methods have been conducted, such as simple oxides and dicarbides. Molecular-line observations have shown that some of these exotic species are present in circumstellar material, defying thermodynamic predictions, including such highly refractory molecules as VO and FeCN. At the very late stages of stellar evolution, the planetary nebula phase, a wide variety of carbon-containing molecules appear to be present, ranging from CCH and c-C3H2 to C60, despite the presence of very high ultraviolet radiation fields. The chemical formation of this wide variety of chemical compounds will be discussed, including a novel mechanism for fullerene production in circumstellar environments.