We study the impact of contact interactions involving two leptons (electrons or muons) and two $b$-quarks ($b \bar{b} \ell^+ \ell^-$) on the high-mass di-lepton region at the LHC. We consider different selections of $b$-tagged jet multiplicities in the di-lepton final states: inclusive (no selection), 0, 1 and 2 $b$-tagged jets, and show that the single $b$-jet selection significantly improves the sensitivity to New Physics (NP) in the form of the $b \bar{b} \ell^+ \ell^-$ contact term. We obtain a better sensitivity compared to the currently existing searches of NP in the di-lepton inclusive channel. In particular, the expected limits go beyond competitive bounds set by LEP (for electrons) on the scale of new physics, $\Lambda$, by a factor of $1.2-3.1$, depending on the chirality structure of the operator. In addition, the expected limits on $\Lambda$, set by using a non-resonant LHC di-lepton inclusive search, are expected to be improved by a factor of $1.3-1.4$ for both electrons and muons.