Abstract: The previous models for reliability and performance of grid services assume that all the states of resource nodes and links are s-independent. This assumption can simplify the modeling and analysis. However it limits the applicability of the models because all the states of resource nodes and links in fact are s-dependent and follow the multivariate exponential distribution. In order to address this issue, this paper presents a novel model for reliability and performance of tree-structured grid service based on multivariate exponential distribution, which assumes that all the states of resource nodes and links are s-dependent and follow the multivariate exponential distribution. Based on the model, a novel algorithm for evaluating the grid service performance distribution and the service reliability indices is suggested. This algorithm constructs a tree of disjoint products and gets the solution of model in the form of disjoint products. The illustrative example and experimental results show that the proposed model for reliability and performance of tree-structured grid service based on multivariate exponential distribution can not only be compatible with previous tree-structured grid service model but also be adapt to the complex grid services in which all the states of resource nodes and links are s-dependent and follow the multivariate exponential distribution; and that the novel algorithm based on tree of disjoint products outperforms the previous algorithms.