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.[Figure not available: see fulltext.].