UBTD1 is a previously uncharacterized ubiquitin-like (UbL) domain containing protein with high homology to the mitochondrial Dc-UbP/UBTD2 protein. Here we show that UBTD1 and UBTD2 belong to a family of proteins that is conserved through evolution and found in metazoa, funghi, and plants. To gain further insight into the function of UBTD1, we screened for interacting proteins. In a yeast-2-hybrid (Y2H) screen, we identified several proteins involved in the ubiquitylation pathway, including the UBE2D family of E2 ubiquitin conjugating enzymes. An affinity capture screen for UBTD1 interacting proteins in whole cell extracts also identified members of the UBE2D family. Biochemical characterization of recombinant UBTD1 and UBE2D demonstrated that the two proteins form a stable, stoichiometric complex that can be purified to near homogeneity. We discuss the implications of these findings in light of the ubiquitin proteasome system (UPS).