We perform a comprehensive study of the impact of new-physics operators with different Lorentz structures on CP-violating observables involving the b → sμ+μ- transition. We examine the effects of new vector-axial vector (VA), scalar-pseudoscalar (SP) and tensor (T) interactions on the CP asymmetries in the branching ratios and forwardbackward asymmetries of Bo s → μ+μ -, Bo d Xs +μ -, Bo s → μ+μ -γ, Bo d → Kμ+μ -, and Bo d → K*μ+μ -. In Bo d → K*μ+μ -, we also explore the direct CP asymmetries in the longitudinal polarization fraction fL and the angular asymmetries A (2) T and ALT, as well as the triple-product CP asymmetries A(im) T and A(im) LT. We find that, in almost all cases, the CP-violating observables are sensitive only to new physics which involves VA operators. The VA new physics may therefore be unambiguously identified by a combined analysis of future measurements of these CP-violating observables. © SISSA 2011.