We leverage tensegrity structures as wheels for a mobile robot that can actively change its shape by expanding or collapsing the wheels. Besides the shape-changing capability, using tensegrity as wheels offers several advantages over traditional wheels of similar size, such as shock-absorbing capability without added mass since tensegrity wheels are both lightweight and highly compliant. We show that a robot with two icosahedron tensegrity wheels can reduce its width from 400 mm to 180 mm and simultaneously increase its height from 75 mm to 95 mm by changing the expanded tensegrity wheels to collapsed disk-like ones. The tensegrity wheels enable the robot to overcome steps with heights up to 110 mm and 150 mm with the expanded and collapsed configuration, respectively. The robot can also jump onto obstacles up to 300 mm high with a bistable mechanism that can gradually store but quickly release energy. We demonstrate the robot's locomotion capability in indoor and outdoor environments, including various natural terrains, like sand, grass, rocks, ice, and snow. Our results suggest that using tensegrity structures as wheels for mobile robots can enhance their capability to overcome obstacles, traverse challenging terrains, and survive falls from heights. When combined with other locomotion modes (e.g., jumping), such shape-changing robots can have broad applications for search-and-rescue after disasters or surveillance and monitoring in unstructured environments.