Road deterioration inspires researchers to enhance the properties of asphalt binder for better performing mixes. Recycled tire rubber, or crumb rubber modifier (CRM), and used motor oil (UMO) are two modifiers that enhance asphalt binder performance through two different mechanisms. CRM affects high-temperature properties while UMO modifies low-temperature properties. Potential environmental concerns arising from the use of UMO have been raised in the literature. In this paper, the two recycled materials were investigated for their ability to complement each other. Both performance benefits of using both materials and the environmental concerns of using UMO were studied. Four CRM asphalt binders were investigated: two with UMO and two without UMO. Environmental impacts were evaluated using gas chromatography to check air emissions for benzene, toluene, ethyl-benzene, and xylenes (BTEX). The potential for toxic leaching of elements from modified hot mix asphalt (HMA) were checked using the US Environmental Protection Agency (EPA) Toxicity Characteristic Leaching Protocol (TCLP). For asphalt binders modified by CRM-UMO combinations, CRM decreased the amounts of released BTEX components, presumably by absorbing UMO and slowing the release of BTEX. Leaching results concluded that UMO mixtures showed a notable percentage of sulfur (S) as compared to non-UMO mixes. All these leachate components were under EPA limits.