In this paper, we present legged walking gaits for an amphibious reconfigurable robot based on a novel eccentric paddle mechanism (ePaddle). The ePaddle mechanism is a novel mechanism that is versatility in locomotion gaits. Five principal kinds of gaits can be achieved, including wheel-like rolling, legged walking, wheel-leg-integrated rolling, and two aquatic paddling gaits. We focus on two types of legged gaits among those possible gaits in this paper. The first one is adopted from a crawl gait that was designed originally for an open-link-based quadrupedal robot. The second legged gait that we introduce is a novel gait which has a duty factor up to 1.0 and keeps a larger static stability margin. The detailed motion planning methods are introduced and verified by simulations and experiments.