Decays of the $Xi_b^-$ and $Omega_b^-$ baryons to the charmless final states $p h^{-}h^{prime -}$, where $h^{(prime)}$ denotes a kaon or pion, are searched for with the LHCb detector. The analysis is based on a sample of proton-proton collision data collected at centre-of-mass energies $sqrt{s} = 7$ and $8 TeV$, corresponding to an integrated luminosity of $3 {rm fb}^{-1}$. The decay $Xi_b^- to p K^-K^-$ is observed with a significance of $8.7$ standard deviations, and evidence at the level of $3.4$ standard deviations is found for the $Xi_b^- to p K^-pi^-$ decay. Results are reported, relative to the $B^-to K^+K^-K^-$ normalisation channel, for the products of branching fractions and $b$-hadron production fractions. The branching fractions of $Xi_b^- to p K^-pi^-$ and $Xi_b^- to p pi^-pi^-$ relative to $Xi_b^- to p K^-K^-$ decays are also measured.