Reliability prediction is an important task in software reliability engineering, which has been widely studied in the last decades. However, modelling and predicting user-perceived reliability of black-box services remain an open research problem. Software services, such as Web services and Web APIs, generally provide black-box functionalities to users through the Internet, thus leading to a lack of their internal information for reliability analysis. Furthermore, the user-perceived service reliability depends not only on the service itself, but also heavily on the invocation context (e.g., service workloads, network conditions), whereby traditional reliability models become ineffective and inappropriate. To address these new challenges posed by blackbox services, in this paper, we propose CARP, a new contextaware reliability prediction approach, which leverages historical usage data from users to construct context-aware reliability models and further provides online reliability prediction results to users. Through context-aware reliability modelling, CARP is able to alleviate the data sparsity problem that heavily limits the prediction accuracy of other existing approaches. The preliminary evaluation results show that CARP can make a significant improvement in reliability prediction accuracy, e.g., about 41% in MAE and 38% in RMSE when only 5% of the data are available.