In this paper we address the rendezvous problem between an autonomous underwater vehicle (AUV) and a pas- sively floating drifter on the sea surface. The AUV’s mission is to keep an estimate of the floating drifter’s position while exploring the underwater environment and periodically attempting to rendezvous with it. We are interested in the case where the AUV loses track of the drifter, predicts its location and searches for it in the vicinity of the predicted location. We parameterize this search problem with respect to both the uncertainty in the drifter’s position estimate and the ratio between the drifter and the AUV speeds. We examine two search strategies for the AUV, an inward spiral and an outward spiral. We derive conditions under which these patterns are guaranteed to find a drifter, and we empirically analyze them with respect to different parameters in simulation. In addition, we present results from field trials in which an AUV successfully found a drifter after periods of communication loss during which the robot was exploring.