The design, optimisation and construction of an anti-coincidence veto detector to complement the ZEPLIN-III direct dark matter search instrument is described. One tonne of plastic scintillator is arranged into 52 bars individually read out by photomultipliers and coupled to a gadolinium-loaded passive polypropylene shield. Particular attention has been paid to radiological content. The overall aim has been to achieve a veto detector of low threshold and high efficiency without the creation of additional background in ZEPLIN-III, all at a reasonable cost. Extensive experimental measurements of the components have been made, including radioactivity levels and performance characteristics. These have been used to inform a complete end-to-end Monte Carlo simulation that has then been used to calculate the expected performance of the new instrument, both operating alone and as an anti-coincidence detector for ZEPLIN-III. The veto device will be capable of rejecting over 65% of coincident nuclear recoil events from neutron background in the energy range of interest in ZEPLIN-III. This will reduce the background in ZEPLIN-III from ≃0.4 to ≃0.14 events per year in the WIMP acceptance region, a significant factor in the event of a non-zero observation. Furthermore, in addition to providing valuable diagnostic capabilities, the veto is capable of tagging over 15% for γ-ray rejection, all whilst contributing no significant additional background. In conjunction with the replacement of the internal ZEPLIN-III photomultiplier array, the new veto is expected to improve significantly the sensitivity of the ZEPLIN-III instrument to dark matter, allowing spin-independent WIMP-nucleon cross sections below 10−8 pb to be probed.