Visual surveillance in the maritime domain has been explored for more than a decade. Although it has produced a number of working systems and resulted in a mature technology, surveillance has been restricted to the port facilities or areas close to the coast line assuming a fixed-camera scenario. This paper presents a novel algorithm for open-sea visual maritime surveillance. We explore a challenging situation with a forward-looking camera mounted on a buoy or other floating platform. The proposed algorithm detects, localizes, and tracks ships in the field of view of the camera. Specifically, developed algorithm is uniquely designed to handle rapidly moving camera. Its performance is robust in the presence of a random relatively-large camera motion. In the context of ship detection we developed a new horizon detection scheme for a complex maritime domain. The performance of our algorithm and its comprising elements is evaluated. Ship detection precision of 88% is achieved on a large dataset collected from a prototype system.