A framework for generating coverage paths for marine habitat mapping is proposed in this paper. The framework combines two existing coverage path planning algorithms with new ideas to provide automated, efficient survey paths that take into account the particularities of the application. On one hand, a recent algorithm especially targeted for marine environments is used to generate a survey path of a previously unmapped area. The method has the advantage of minimizing repeated coverage when using a surface vehicle or while surveying at constant depth with an underwater vehicle. On the other hand, only the regions where the marine habitat is present (which often come in the form of widespread “blobs”) need to be surveyed in future monitoring missions in the area. However, due to the changing nature of the marine habitats, determining the exact extent of those regions prior to mission is not possible. Rather than surveying the whole area anew, we propose to use a sensor-based planner that, given their approximate locations from a previous survey, covers the regions of interest (ROIs) on-line using acoustic or optical camera information. Additional procedures to generate a path that visits all the ROIs are provided. The approach is tested in simulation using a real-world bathymetric dataset and synthetic ROIs. Results show the feasibility of the proposed approach.