Submarine oil and gas pipeline inspection is a highly time and cost consuming task. Using an autonomous underwater vehicle (AUV) for such applications represents a great saving potential. However, the AUV navigation system requires reliable localization and stable tracking of the pipeline position. We present a method for robust pipeline localization relative to the AUV in 3D based on stereo vision and echo sounder depth data. When the pipe is present in both camera images, a standard stereo vision approach is used for localization. Enhanced localization continuity is ensured using a second approach when the pipe is segmented out in only one of the images. This method is based on a combination of one camera with depth information from the echo sounder mounted on the AUV. In the algorithm, the plane spanned by the pipe in the camera image is intersected with the plane spanned by the sea floor, to give the pipe position in 3D relative to the AUV. Closed water recordings show that the proposed method localizes the pipe with an accuracy comparable to that of the stereo vision method. Furthermore, the introduction of a second pipe localization method increases the true positive pipe localization rate by a factor of four.