The mitochondrial calcium uniporter complex (MCUC) is a highly selective channel that conducts calcium ions across the organelle inner membrane. We previously characterized Trypanosoma brucei’s MCU (TbMCU) as an essential component of the MCUC required for parasite viability and infectivity. In this study, we characterize its paralog T. brucei MCUb (TbMCUb) and report the identification of two novel components of the complex that we named TbMCUc and TbMCUd. These new MCUC proteins are unique and conserved only in trypanosomatids. In situ tagging and immunofluorescence microscopy revealed that they colocalize with TbMCU and TbMCUb to the mitochondria of T. brucei. Blue Native PAGE and immunodetection analyses indicated that the MCUC proteins exist in a large protein complex with a molecular weight of approximately 380 kDa. RNA interference (RNAi) or overexpression of the TbMCUc and TbMCUd genes significantly reduced or enhanced mitochondrial Ca2+uptake in T. brucei, respectively, without affecting the mitochondrial membrane potential, indicating that they are essential components of the MCUC of this parasite. The specific interactions of TbMCU with TbMCUb, TbMCUc, or TbMCUd were confirmed by coimmunoprecipitation and split-ubiquitin membrane-based yeast two-hybrid (MYTH) assays. Furthermore, combining mutagenesis analysis with MYTH assays revealed that transmembrane helices (TMHs) were determinant of the interactions between TbMCUC subunits. In summary, our study has identified two novel essential components of the MCUC of T. brucei and defined their direct physical interactions with the other subunits that result in a hetero-oligomeric MCUC.