At present, there are several measurements of B decays that exhibit discrepancies with the predictions of the SM, and suggest the presence of new physics (NP) in b→sμ+μ- transitions. Many NP models have been proposed as explanations. These involve the tree-level exchange of a leptoquark (LQ) or a flavor-changing Z′ boson. In this paper we examine whether it is possible to distinguish the various models via CP-violating effects in B→K(∗)μ+μ-. Using fits to the data, we find the following results. Of all possible LQ models, only three can explain the data, and these are all equivalent as far as b→sμ+μ- processes are concerned. In this single LQ model, the weak phase of the coupling can be large, leading to some sizable CP asymmetries in B→K(∗)μ+μ-. There is a spectrum of Z′ models; the key parameter is gLμμ, which describes the strength of the Z′ coupling to μ+μ-. If gLμμ is small (large), the constraints from Bs0-B-s0 mixing are stringent (weak), leading to a small (large) value of the NP weak phase, and corresponding small (large) CP asymmetries. We therefore find that the measurement of CP-violating asymmetries in B→K(∗)μ+μ- can indeed distinguish among NP b→sμ+μ- models. © 2017 American Physical Society.