Predicting protein submitochondrial locations has been studied for about ten years. A dozen of methods were developed in this regard. Although a mitochondrion has four submitochondrial compartments, all existing studies considered only three of them. The mitochondrial intermembrane space proteins were always excluded in these studies. However, there are over 50 mitochondrial intermembrane space proteins in the recent release of UniProt database. We think it is time to incorporate these proteins in predicting protein submitochondrial locations. We proposed the functional domain enrichment score, which can be used as an enhancement to our positional-specific physicochemical properties method. We constructed a high-quality working dataset from the UniProt database. This dataset contains proteins from all four submitochondrial locations. Proteins with multiple submitochondrial locations are also included. Our method achieved over 70% prediction accuracy for proteins with single location on this dataset. On the M3-317 benchmarking dataset, our method achieved comparable prediction performance to other state-of-the-art methods. Our results indicate that the intermembrane space proteins can be incorporated in predicting protein submitochondrial locations. By evaluating our method with the proteins that have multiple submitochondrial locations, we conclude that our method is capable of predicting multiple submitochondrial locations. This is the first report of ab initio methods that can identify intermembrane space proteins. This is also the first attempt to incorporate proteins with multiple submitochondrial locations. The benchmarking dataset can be obtained by emails to the corresponding author.