The Kac-Ward formula allows to compute the Ising partition function on a planar graph G with straight edges from the determinant of a matrix of size 2N, where N denotes the number of edges of G. In this paper, we extend this formula to any finite graph: the partition function can be written as an alternating sum of the determinants of 2^{2g} matrices of size 2N, where g is the genus of an orientable surface in which G embeds. We give two proofs of this generalized formula. The first one is purely combinatorial, while the second relies on the Fisher-Kasteleyn reduction of the Ising model to the dimer model, and on geometric techniques. As a consequence of this second proof, we also obtain the following fact: the Kac-Ward and the Fisher-Kasteleyn methods to solve the Ising model are one and the same.