We introduce and discuss a quantifier of phase-space complexity for continuous-variable (CV) and discrete-variable (DV) quantum systems. The complexity measure of quantum states is based on the Husimi Q-function defined over coherent states, and the quantifier combines into a single scalar quantity two complementary information-theoretic quantities: the Wehrl entropy, which captures phase-space spread, and the Fisher information, which captures localization. We derive fundamental properties of the measure for CV and DV systems, use it to quantify the complexity of quantum channels, and illustrate its properties with several examples. Finally, we briefly illustrate work in progress towards extending the measure from phase-space to Hilbert space.