In this paper, we propose a novel object detection algorithm for underwater environments exploiting multiscale graph-based segmentation. The graph-based approach to image segmentation is fairly independent from distortion, color alteration and other peculiar effects arising with light propagation in water medium. The algorithm is executed at different scales in order to capture both the contour and the general shape of the target cylindrical object. Next, the candidate regions extracted at different scales are merged together. Finally, the candidate region is validated by a shape regularity test. The proposed algorithm has been compared with a color clustering method on an underwater dataset and has achieved precise and accurate detection.