Several essential biochemical processes are situated in mitochondria. The metabolic transformation of mitochondria in distinct lineages of eukaryotes created proteomes ranging from thousands of proteins to what appear to be a much simpler scenario. In the case of Entamoeba histolytica, tiny mitochondria known as mitosomes have undergone extreme reduction. Only recently a single complete metabolic pathway of sulfate activation has been identified in these organelles. The E. histolytica mitosomes do not produce ATP needed for the sulfate activation pathway and for three molecular chaperones, Cpn60, Cpn10 and mtHsp70. The already characterized ADP/ATP carrier would thus be essential to provide cytosolic ATP for these processes, but how the equilibrium of inorganic phosphate could be maintained was unknown. Finally, how the mitosomal proteins are translocated to the mitosomes had remained unclear. We used a hidden Markov model (HMM) based search of the E. histolytica genome sequence to discover candidate (i) mitosomal phosphate carrier complementing the activity of the ADP/ATP carrier and (ii) membrane-located components of the protein import machinery that includes the outer membrane translocation channel Tom40 and membrane assembly protein Sam50. Using in vitro and in vivo systems we show that E. histolytica contains a minimalist set up of the core import components in order to accommodate a handful of mitosomal proteins. The anaerobic and parasitic lifestyle of E. histolytica has produced one of the simplest known mitochondrial compartments of all eukaryotes. Comparisons with mitochondria of another amoeba, Dictystelium discoideum, emphasize just how dramatic the reduction of the protein import apparatus was after the loss of archetypal mitochondrial functions in the mitosomes of E. histolytica.