The strong linkage of electric power and heat supplies can be decoupled to reduce wind power curtailment by exploiting the energy storage and regulation capabilities of the district heating network (DHN), electric boilers and heat storage tanks. In this paper, the coordinated dispatch of integrated electrical and heating systems (CDIEHS), considering the energy storage of both pipelines in the DHN and heat storage tanks, is formulated as a convex quadratic program. Since the electric power system (EPS) and the district heating system (DHS) are controlled separately by different operation organizations, CDIEHS is solved in a decentralized manner using optimality condition decomposition (OCD). The OCD algorithm, with guaranteed convergence for convex programs, can achieve a fully distributed solution for the CDIEHS and requires only minor boundary information exchange between the EPS and the DHS. The simulation results are discussed for two test systems, including a real power system, to demonstrate the effectiveness of the proposed decentralized method, which achieves the same solution as the centralized method in a moderate number of iterations.