The first observation of $Z$ boson production in proton-lead collisions at a centre-of-mass energy per proton-nucleon pair of $sqrt{s_{NN}}=5~text{TeV}$ is presented. The data sample corresponds to an integrated luminosity of $1.6~text{nb}^{-1}$ collected with the LHCb detector. The $Z$ candidates are reconstructed from pairs of oppositely charged muons with pseudorapidities between 2.0 and 4.5 and transverse momenta above $20~text{GeV}/c$. The invariant dimuon mass is restricted to the range $60-120~text{GeV}/c^2$. The $Z$ production cross-section is measured to be begin{eqnarray*} sigma_{Ztomu^+mu^-}(text{fwd})&=&13.5^{+5.4}_{-4.0}text{(stat.)}pm1.2text{(syst.)}~text{nb} end{eqnarray*} in the direction of the proton beam and begin{eqnarray*} sigma_{Ztomu^+mu^-}(text{bwd}) & =&10.7^{+8.4}_{-5.1}text{(stat.)}pm1.0text{(syst.)}~text{nb} end{eqnarray*} in the direction of the lead beam, where the first uncertainty is statistical and the second systematic.