A search for charmless four-body decays of Λ b 0 and Ξ b 0 baryons with a proton and three charged mesons (either kaons or pions) in the final state is performed. The data sample used was recorded in 2011 and 2012 with the LHCb experiment and corresponds to an integrated luminosity of 3 fb−1. Six decay modes are observed, among which Λ b 0  → pK−π+π−, Λ b 0  → pK−K+K−, Ξ b 0  → pK−π+π− and Ξ b 0  → pK−π+K− are established for the first time. Their branching fractions (including the ratio of hadronisation fractions in the case of the Ξ b 0 baryon) are determined relative to the Λ b 0  → Λ c + π− decay.