Fish detection is the upstream module of the whole Fish4Knowledge system and, as such, it needs to be as accurate and fast as possible. Driven by these needs, several state of the art and new approaches for object segmentation in videos have been developed and tested. We opted for background modeling —based approaches as they fit better with the underwater domain peculiarities. In particular, kernel density estimation methods, modeling colors, texture and spatial information of both the background and the foreground, proved to be the best performing ones not only in underwater video sequences but also in other complex scenarios. To provide more robustness to fish detection, we also developed a post-processing layer (added on top of the background modeling one) able to filter out effectively false detections by using "real-world" object properties. Despite the low-quality (low frame rate and spatial resolution) of the processed underwater videos, the achieved results can be considered satisfactory especially considering that most of the state of the art approaches failed. This chapter provides, therefore, an overview on the development and deployment of fish detection module for the Fish4Knowledge system. It includes a detailed analysis of the challenges of underwater video analysis , the limitations of the existing approaches, the devised solutions and the experimental results.