Multistage interconnection networks (MINs) are widely used for reliable data communication in tightly coupled large‐scale multiprocessor systems. Reliability evaluation of interconnection networks is still a challenge owing to high complexity. Need of reliability evaluation for MINs is quite evident as these measures provide user‐oriented performance. Terminal pair reliability (TPR) is the most commonly used reliability performance index of MINs. This paper provides a global view of different reliability measures and approaches for evaluation of these measures. Based on the critical literature review, shortcomings are identified and analyzed. Then the multi‐variable inversion algorithm is applied to evaluate the reliability of one of the most common MINs, namely, Omega network, in a compact form. Terminal, broadcast, and network reliability for the Omega, Omega with an additional stage (Omega+), and Omega with two additional stages (Omega+2) systems are analyzed and compared. Then we extend our work to trace the minimal path sets of various MINs, and terminal pair reliabilities are evaluated and compared. Copyright © 2015 John Wiley & Sons, Ltd.