We report on a 3D electron beam lithography (EBL) technique using polymethyl methacrylate (PMMA) in the negative-tone regime as a resist. First, we briefly demonstrate 3D EBL at room temperature. Then we concentrate on cryogenic temperatures where PMMA exhibits a low contrast, which allows for straightforward patterning of 3D nano- and microstructures. However, conventional EBL patterning at cryogenic temperatures is found to cause severe damage to the microstructures. Through an extensive study of lithography parameters, exposure techniques, and processing steps we deduce a hypothesis for the cryogenic PMMA's structural evolution under electron beam irradiation that explains the damage. In accordance with this hypothesis, a two step lithography technique involving a wide-area pre-exposure dose slightly smaller than the onset dose is applied. It enables us to demonstrate a >95% process yield for the low-temperature fabrication of 3D microstructures.