Many organisms, including various species of spiders and caterpillars, change their shape to switch gaits and adapt to different environments. Recent technological advances, ranging from stretchable circuits to highly deformable soft robots, have begun to make shape-changing robots a possibility. However, it is currently unclear how and when shape change should occur, and what capabilities could be gained, leading to a wide range of unsolved design and control problems. To begin addressing these questions, here we simulate, design, and build a soft robot that utilizes shape change to achieve locomotion over both a flat and inclined surface. Modeling this robot in simulation, we explore its capabilities in two environments and demonstrate the existence of environment-specific shapes and gaits that successfully transfer to the physical hardware. We found that the shape-changing robot traverses these environments better than an equivalent but non-morphing robot, in simulation and reality.