In this work, we explore the flavor-changing decays Hi→bs in a general supersymmetric scenario. In these models the flavor-changing decays arise at loop level, but¿because they originate from a dimension-four operator¿they do not decouple and may provide a first sign of new physics for heavy masses beyond the reach of colliders. In the framework of the minimal supersymmetric extension of the Standard Model, we find that the largest branching ratio of the lightest Higgs (H1) is O(10−6) after imposing present experimental constraints, while heavy Higgs states may still present branching ratios O(10−3). In a more general supersymmetric scenario, where additional Higgs states may modify the Higgs mixings, the branching ratio BR(H1→bs) can reach values O(10−4), while heavy Higgses still remain at O(10−3). Although these values are clearly out of reach for the LHC, a full study in a linear collider environment could be worth pursuing.