  We study constraints and implications of the recent LHCb measurement of
${\cal B}(B_s \to \mu^+\mu^-)$ for tree-level Higgs-mediated flavor-changing
neutral current (FCNC) interactions. Combined with experimental data on $B_s$
mass difference $\Delta m_s$, the $h \to \mu \tau$, and the $h \to
\tau^+\tau^-$ decay branching ratios from the LHC, we find that the Higgs FCNC
couplings are severely constrained. The allowed regions for $B_s \to \mu \tau$,
$\tau\tau$ and $h \to sb$ decays are obtained. Current data allow large CP
violation in the $h \to \tau^+ \tau^-$ decay. Consequences of the Cheng-Sher
ansatz for the Higgs Yukawa couplings are discussed in some detail.
