We consider the most general new physics effective Lagrangian for b→sl+l-. We derive the upper limit on the branching ratio for the processes Bs→l+l- where l=e,μ, subject to the current experimental bounds on related processes, B→Kl+l- and B→K*l+l -. If the new physics interactions are of vector/axial-vector form, the present measured rates for B→(K,K*;)l+l- constrain B(Bs→l+l-) to be of the same order of magnitude as their respective Standard Model predictions. On the other hand, if the new physics interactions are of scalar/pseudoscalar form, B→(K,K*)l+l- rates do not impose any constraint on Bs→l+l- and the branching ratios of these decays can be as large as present experimental upper bounds. If future experiments measure B(Bs→l+l-) to be ≥10-8 then the new physics giving rise to these decays has to be of the scalar/pseudoscalar form.