We map out the critical velocity in the crossover from Bose-Einstein condensation to Bardeen-Cooper-Schrieffer superfluidity with ultracold Li6 gases. A small attractive potential is dragged along lines of constant column density. The rate of the induced heating increases steeply above a critical velocity vc. In the same samples, we measure the speed of sound vs by exciting density waves and compare the results to the measured values of vc. We perform numerical simulations in the Bose-Einstein condensation regime and find very good agreement, validating the approach. In the strongly correlated regime our measurements of vc provide a testing ground for theoretical approaches.