Crawling robots are advantageous in overcoming obstacles. These robots have characteristics such as light weight and outstanding mobility. In case of large robots, they have difficulties passing narrow gaps or entering the cave. In this paper, we propose a milli-scale hexapedal robot using 4-bar linkages. Two conditions are necessary to enable efficient walking. In short, the trajectory of the foot must be elliptical, and the lowest point of the foot should be the same. These conditions are satisfied with a novel leg design. The robot has a pair of three legs and the legs are coupled to operate simultaneously. Each set of the legs are installed to robot’s both sides and the legs satisfy the equal lowest foot point and elliptical trajectory. As a result, this hexapedal robot can crawl with 0.56m/s speed.