The paper deals with the problem of underwater localization for Autonomous Underwater Vehicles (AUVs) by using a set of acoustic transponders located in known fixed positions. More specifically, the work proposes an effective technique for enabling an AUV to on-line estimate its 3D position, by only employing the measurements of the Time-of-Flights (ToFs) of the signals exchanged with the transponders, without any a-priori information on the Speed of Sound (SoS) of the considered water area. The value of SoS is indeed considered as an additional unknown parameter within the estimation procedure. For any set of received ToFs, a cost function (dependent on the AUV coordinates and the SoS value) is defined and minimized via a standard gradient-descent technique. The optimization process exhibits very good properties in terms of speed of convergence, thanks to the simple structure of the considered cost function. The algorithm has been first tested in a simulated environment and then experimentally validated on an eFOLAGA AUV interrogating four Hydroid transponders.