We propose the Wigner separability entropy as a measure of complexity of a quantum state. This quantity measures the number of terms that effectively contribute to the Schmidt decomposition of the Wigner function with respect to a chosen phase-space decomposition. We prove that the Wigner separability entropy is equal to the operator space entanglement entropy, measuring entanglement in the space of operators, and, for pure states, twice the entropy of entanglement. The quantum to classical correspondence between the Wigner separability entropy and the separability entropy of the classical phase-space Liouville density is illustrated by means of numerical simulations of chaotic maps. In this way, the separability entropy emerges as an extremely broad complexity quantifier in both the classical and quantum realms.