We present a search for neutrinos in coincidence in time and direction with four fast radio bursts (FRBs) detected by the Parkes and Green Bank radio telescopes during the first year of operation of the complete IceCube Neutrino Observatory (2011 May through 2012 May). The neutrino sample consists of 138,322 muon neutrino candidate events, which are dominated by atmospheric neutrinos and atmospheric muons but also contain an astrophysical neutrino component. Considering only neutrinos detected on the same day as each FRB, zero IceCube events were found to be compatible with the FRB directions within the estimated 99% error radius of the neutrino directions. Based on the non-detection, we present the first upper limits on the neutrino fluence from FRBs.