Developing untethered millirobots that can adapt to harsh environments with high locomotion efficiency is of interest for emerging applications in various industrial and biomedical settings. Despite recent success in exploiting soft materials to impart sophisticated functions which are not available in conventional rigid robotics, it remains challenging to achieve superior performances in both wet and dry conditions. Inspired by the flexible, soft, and elastic leg/foot structures of many living organisms, here we report an untethered soft millirobot decorated with multiple tapered soft feet architecture. Such robot design yields superior adaptivity to various harsh environments with ultrafast locomotion speed (>40 limb length/s), ultra-strong carrying capacity (>100 own weight), and excellent obstacle-crossing ability (stand up 90° and across obstacle >10 body height). Our work represents an important advance in the emerging area of bio-inspired robotics and will find a wide spectrum of applications.