We have performed a search for CP violation in a sample of Bs -> Ds mu X decays corresponding to $5$~fb$^{-1}$ of proton-antiproton collisions collected by the D0 detector in Run~II at the Fermilab Tevatron Collider. New physics in $B_s^0$ mixing could contribute a significant CP violating weak phase, which would be observed as a difference in the decay-time distribution for $B_s^0\to \bar{B}_s^0$ oscillated states versus that for $\bar{B}_s^0\to {B}_s^0$. A fit to the decay-time distributions of the $B_s^0/\bar{B}_s^0$ candidates yields the flavor-specific asymmetry $a_{fs}^{s}=[-1.7\pm 9.1\mathrm{(stat)}^{+1.4}_{-1.5}\mathrm{(syst)}] \times 10^{-3}$, which excludes CP violation due to new physics within the experimental sensitivity.