Amphibious robots have attracted more and more attention from researchers for their broad applications, while it also brings great challenges in designing appropriate propulsion mechanisms and effective control algorithms. In this paper, we reported a newly designed amphibious hexapod robot-AmphiHex-II. This robot possesses six newly designed variable stiffness legs for adapting various complex environments. This novel design of the variable stiffness leg seamlessly incorporates the advantages of both semi-circular walking legs and the swimming flexible flippers. The legs are constructed by rigid fan-shaped frames which work as walking legs for terrestrial locomotion and protect the contained flexible flippers used for aquatic locomotion during terrestrial operations. The stiffness of legs can be adjusted to an effective degree by adjusting the positions of sliders manually. The effect of variable stiffness on locomotion performance was experimentally investigated. Moreover, in order to achieve a smooth and quick gait transition, a Central Pattern Generator (CPG) neural network was introduced to control the system. Different gait generation strategies on land and underwater were demonstrated. A series of field experiments were carried out to evaluate locomotion performance of the AmphiHex-II for terrestrial and aquatic mobility, and the results demonstrate the advantages of the novel leg design and the control system.