  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.
