Wireless soft-bodied robots at the millimeter scale allow traversing very confined unstructured terrains with minimal invasion and safely interacting with the surrounding environment. However, existing untethered soft millirobots still lack the ability of climbing, reversible controlled surface adhesion, and long-term retention on unstructured three-dimensional (3D) surfaces, limiting their use in biomedical and environmental applications. Here, we report a fundamental peeling-and-loading mechanism to allow untethered soft-bodied robots to climb 3D surfaces by using both the soft-body deformation and whole-body motion of the robot under external magnetic fields. This generic mechanism is implemented with different adhesive robot footpad designs, allowing vertical and inverted surface climbing on diverse 3D surfaces with complex geometries and different surface properties. With the unique robot footpad designs that integrate microstructured adhesives and tough bioadhesives, the soft climbing robot could achieve controllable adhesion and friction to climb 3D soft and wet surfaces including porcine tissues, which paves the way for future environmental inspection and minimally invasive medicine applications.