We report the results of a multimessenger search for coincident signals from the LIGO and Virgo gravitational-wave observatories and the partially completed IceCube high-energy neutrino detector, including periods of joint operation between 2007–2010. These include parts of the 2005–2007 run and the 2009–2010 run for LIGO-Virgo, and IceCube’s observation periods with 22, 59 and 79 strings. We find no significant coincident events, and use the search results to derive upper limits on the rate of joint sources for a range of source emission parameters. For the optimistic assumption of gravitational-wave emission energy of 10−2  M⊙c2 at ∼150  Hz with ∼60  ms duration, and high-energy neutrino emission of 1051  erg comparable to the isotropic gamma-ray energy of gamma-ray bursts, we limit the source rate below 1.6×10−2  Mpc−3 yr−1. We also examine how combining information from gravitational waves and neutrinos will aid discovery in the advanced gravitational-wave detector era. © 2014 The American Physical Society