Reliability prediction for Service-Oriented Systems (SOSs) can reduce the occurrence of emergencies and ensure the stable operation of systems. In this paper, a reliability prediction method for SOSs is proposed. Firstly, service dependency graph of SOSs is constructed based on service dependency relationship described by CA-CCML (Context-Aware Cooperative Composition Modeling Language) service composition model. Then, an IW-LeaderRank (Improved Weighted LeaderRank) algorithm is adopted to measure the importance of nodes in the service dependency graph and further to identify the critical components of SOSs. After that, a component reliability prediction model for SOSs based on Attention-LSTM network is proposed. Meanwhile, the critical services composition model graph is constructed using Depth-First-Search algorithm to describe composition structures among the identified critical components. Finally, the reliability prediction value of SOSs is calculated by using those of critical components and their composition structures. Experiments show that the proposed reliability prediction method for SOSs has obvious advantages in accuracy and efficiency.