Anguilliform swimmers, like eels or lampreys, are highly efficient swimmers. Key to understanding their performances is the relationship between the body’s kinematics and resulting swimming speed and efficiency. But, we cannot prescribe kinematics to living fish, and it is challenging to measure their power consumption. Here, we characterise the swimming speed and cost of transport of a free-swimming undulatory bio-inspired robot as we vary its kinematic parameters, including joint amplitude, body wavelength, and frequency. We identify a trade-off between speed and efficiency. Speed, in terms of stride length, increases for increasing maximum tail angle, described by the newly proposed specific tail amplitude and reaches a maximum value around the specific tail amplitude of unity. Efficiency, in terms of the cost of transport, is affected by the whole-body motion. Cost of transport decreases for increasing travelling wave-like kinematics, and lower specific tail amplitudes. Our results suggest that live eels tend to choose efficiency over speed and provide insights into the key characteristics affecting undulatory swimming performance.