Animals use a variety of gaits to locomote. For most species, a change in gait involves use of different movement in the same medium -e.g. switching from trotting to galloping in horses or paired fin to axial swimming in fishes. Some species switch gaits by also changing their physical environment for movement. Best known are birds that transition between terrestrial gaits and flight. For aquatic organisms, gait transitions analogous to those of birds occur in a range of animals that can locomote on the bottom substrate and swim. Here, we examine the walking and jetting and the walk-to-jet gait transition of young California two-spot octopus, Octopus bimaculoides. At low speeds, octopus use their arms to walk on the bottom substrate. Our data indicate that at faster walking speeds, water pumped from the siphon augments arm-based force generation to facilitate walking, particularly in the backward direction and to the side. The transition from walking to jet-based swimming occurred when animals were walking backward in the direction of the position four arms. In the transition to fully jet-driven swimming, right four and/or left four arms frequently were the last planted and appeared to push off at the initiation of swimming. During jet-based swimming, the arms extended together trailing the body. At the end of swimming, animals frequently initiated substrate contact with one arm before splaying the others and initiating substrate-based walking. Understanding this very different and independently evolved gait transition and comparing it to locomotion in other animals provides insight into the evolution of gait use and coordination and informs investigation of the neural control of movement.