This paper describes an obstacle detection and tracking algorithm applied to multibeam forward-looking sonar images. It is used by an obstacle avoidance system to be fitted in a Remotely Operated underwater Vehicle (ROV). The real-time data flow from the sonar output is represented as an image and pre-processed (smoothing filters, region-based segmentation and feature extraction) by the system to identify possible obstacles. Regionbased segmentation has been chosen due to the noisy nature of sonar images, where line and point features are difficult to detect. The obstacles are then tracked by applying a Kaiman filter to each one. We use a nearest neighbour algorithm to associate new predictions to new obstacles in the scene. In subsequent frames the pre-processing phase is optimised by limiting the amount of processed data to those parts of the images where the obstacles are predicted to appear. New obstacles are also constantly being detected by less cumbersome segmentation methods (subsampled images, smaller window smoothing, and simple thresholding). The algorithm performs consistently well using real data sets from two different sonar sensors. A major constraint for the system was to perform in real-time. Indeed, previous work in the Ocean Systems Laboratory, Heriot-Watt University, based in standard vision optical flow techniques proved to be too costly in terms of processing power. These problems have now been solved without jeopardising the quality of the results. We present results of tracking using real data sets and discuss possible implementations.