The rare decay $B^0_s\rightarrow \mu^+ \mu^-$ provides a powerful probe of physics beyond the Standard Model due to its strong suppression and sensitivity to flavor-changing neutral current interactions. In this work, we analyze this process in a CP-violating Two-Higgs-Doublet Model with a general Yukawa structure. The most general scalar potential is considered, leading to mixing among the neutral scalar states and resulting in physical Higgs bosons with mixed CP properties. The general Yukawa sector gives rise to flavor-changing neutral scalar interactions at tree level. We derive the corresponding contributions to the branching ratio of $B^0_s\rightarrow \mu^+ \mu^-$ and investigate their dependence on the scalar mixing angles and Yukawa couplings.