New protein structures are continuously being determined with the hope of deriving insights into the function and mechanisms of proteins, and consequently, protein structure repositories are growing by leaps and bounds. However, we are still far from having the right methods for sensitive and effective use of the available structural data. The fact that current structural analysis tools are impractical for large-scale applications have given rise to several approaches that try to quickly identify candidate proteins worthy of further analysis. Nonetheless, these approaches do not provide the desired sensitivity of identifying important structural similarities. In this study, we propose a new protein structure retrieval method (RCIndex: Residue-Contacts Index) that is based on accurate and efficient identification of similar residue contacts from a database of available protein structures. By defining a metric distance function for biologically meaningful comparison of residue contacts, distance-based indexing is made applicable for quick retrieval of similar residue contact seeds. These seeds are extended into high scoring segment pairs, which induce structural superpositions. The results show that RCIndex is effective in not only identifying related proteins, but also producing remarkably high quality structural alignments that are comparable to or better than those produced by popular pairwise alignment tools. To the best of our knowledge, this is the first time the protein structure retrieval and alignment tasks are successfully handled together.