Using a $pp$ collision data sample corresponding to an integrated luminosity of 3.0~fb$^{-1}$, collected by the LHCb detector, we present the first search for the strangeness-changing weak decay $Xi_b^-toLambda_b^0pi^-$. No $b$ hadron decay of this type has been seen before. A signal for this decay, corresponding to a significance of 3.2 standard deviations, is reported. The relative rate is measured to be ${{f_{Xi_b^-}}over{f_{Lambda_b^0}}}{cal{B}}(Xi_b^-toLambda_b^0pi^-) = (5.7pm1.8^{+0.8}_{-0.9})times10^{-4}$, where $f_{Xi_b^-}$ and $f_{Lambda_b^0}$ are the $btoXi_b^-$ and $btoLambda_b^0$ fragmentation fractions, and ${cal{B}}(Xi_b^-toLambda_b^0pi^-)$ is the branching fraction. Assuming $f_{Xi_b^-}/f_{Lambda_b^0}$ is bounded between 0.1 and 0.3, the branching fraction ${cal{B}}(Xi_b^-toLambda_b^0pi^-)$ would lie in the range from $(0.57pm0.21)%$ to $(0.19pm0.07)%$.