We introduce a fully-coherent method for searching for gravitational wave signals generated by the merger of black hole and/or neutron star binaries. This extends the coherent analysis previously developed and used for targeted gravitational wave searches to an all-sky, all-time search. We apply the search to one month of data taken during the fifth science run of the LIGO detectors. We demonstrate an increase in sensitivity of 25% over the coincidence search, which is commensurate with expectations. Finally, we discuss prospects for implementing and running a coherent search for gravitational wave signals from binary coalescence in the advanced gravitational wave detector data.