We develop a theoretical framework to study slowly rotating compact stars in a rather general class of alternative theories of gravity, with the ultimate goal of investigating constraints on alternative theories from electromagnetic and gravitational-wave observations of compact stars. Our Lagrangian includes as special cases scalar-tensor theories (and indirectly f(R) theories) as well as models with a scalar field coupled to quadratic curvature invariants. As a first application of the formalism, we discuss (for the first time in the literature) compact stars in Einstein-Dilaton-Gauss-Bonnet gravity. We show that compact objects with central densities typical of neutron stars cannot exist for certain values of the coupling constants of the theory. In fact, the existence and stability of compact stars sets more stringent constraints on the theory than the existence of black hole solutions. This work is a first step in a program to systematically rule out (possibly using Bayesian model selection) theories that are incompatible with astrophysical observations of compact stars.