A search for a Higgs boson decaying into a Z boson and a photon is described. The analysis is performed using proton-proton collision datasets recorded by the CMS detector at the LHC. Events were collected at center-of-mass energies of 7 TeV and 8 TeV, corresponding to integrated luminosities of 5.0 and 19.6 inverse femtobarns, respectively. The selected events are required to have opposite-sign electron or muon pairs. No excess above standard model predictions has been found in the 120-160 GeV mass range and the first limits on the Higgs boson production cross section times the H to Z gamma branching fraction at the LHC have been derived. The observed at 95% confidence level limits are between about 4 and 25 times the standard model cross section times the branching fraction. For a standard model Higgs boson mass of 125 GeV the expected limit at the 95% confidence level is 10 and the observed limit is 9.5. Models predicting the Higgs boson production cross section times the Higgs to Z gamma branching fraction to be larger than one order of magnitude of the standard model prediction are excluded for most of the 125-157 GeV mass range.