An enhanced ordered binary decision diagram (EOBDD) algorithm is proposed to evaluate the reliability of wireless sensor networks (WSNs), based on the considerations of the common cause failure (CCF) and a large number of nodes in WSNs. The EOBDD algorithm analyzes the common cause event (CCE) and the network structure when CCE takes place according to the stochastic graph and the CCF model of WSNs. After constructing the ordered binary decision diagram (OBDD) of the original network with node expansion, it uses a set of OBDD variables (SOV) to guide reliability computations along this OBDD. The two steps about OBDD can decrease the cost of OBDD constructions and storage. Furthermore, the efficient OBDD structure and Hash tables can greatly decrease redundant computations of isomorphs. The experiment results show that the EOBDD can be used to evaluate the reliability of WSN efficiently.