An important problem in the control of locomotion of robots with multiple degrees of freedom (e.g., biomimetic robots) is to adapt the locomotor patterns to the properties of the environment. This article addresses this problem for the locomotion of an amphibious snake robot, and aims at identifying fast swimming and crawling gaits for a variety of environments. Our approach uses a locomotion controller based on the biological concept of central pattern generators (CPGs) together with a gradient-free optimization method, Powell’s method. A key aspect of our approach is that the gaits are optimized online, i.e., while moving, rather than as an off-line optimization process. We present various experiments with the real robot and in simulation: swimming, crawling on horizontal ground, and crawling on slopes. For each of these different situations, the optimized gaits are compared with the results of systematic explorations of the parameter space. The main outcomes of the experiments are: 1) optimal gaits are significantly different from one medium to the other; 2) the optimums are usually peaked, i.e., speed rapidly becomes suboptimal when the parameters are moved away from the optimal values; 3) our approach finds optimal gaits in much fewer iterations than the systematic search; and 4) the CPG has no problem dealing with the abrupt parameter changes during the optimization process. The relevance for robotic locomotion control is discussed.