A new method based on modified self-organizing maps is presented for the reconstruction of deep ocean current velocities from surface information provided by satellites. This method takes advantage of local correlations in the data-space to improve the accuracy of the reconstructed deep velocities. No assumptions regarding the structure of the water column, nor the underlying dynamics of the flow field, are made. Using satellite observations of surface velocity, sea-surface height and sea-surface temperature, as well as observations of the deep current velocity from autonomous Argo floats to train the map, we are able to reconstruct realistic high-resolution velocity fields at a depth of 1000 m. Validation reveals promising results, with a speed root mean squared error of similar to 2.8 cm.s(-1), more than a factor of two smaller than competing methods, and direction errors consistently smaller than 30 degrees. Finally, we discuss the merits and shortcomings of this methodology.