Two structures are observed close to the kinematic threshold in the $Xi_b^0 pi^-$ mass spectrum in a sample of proton-proton collision data, corresponding to an integrated luminosity of 3.0 fb$^{-1}$ recorded by the LHCb experiment. In the quark model, two baryonic resonances with quark content $bds$ are expected in this mass region: the spin-parity $J^P = frac{1}{2}^+$ and $J^P=frac{3}{2}^+$ states, denoted $Xi_b^{prime -}$ and $Xi_b^{*-}$. Interpreting the structures as these resonances, we measure the mass differences and the width of the heavier state to be $m(Xi_b^{prime -}) - m(Xi_b^0) - m(pi^{-}) = 3.653 pm 0.018 pm 0.006$ MeV$/c^2$, $m(Xi_b^{*-}) - m(Xi_b^0) - m(pi^{-}) = 23.96 pm 0.12 pm 0.06$ MeV$/c^2$, $Gamma(Xi_b^{*-}) = 1.65 pm 0.31 pm 0.10$ MeV, where the first and second uncertainties are statistical and systematic, respectively. The width of the lighter state is consistent with zero, and we place an upper limit of $Gamma(Xi_b^{prime -}) < 0.08$ MeV at 95% confidence level. Relative production rates of these states are also reported.