This paper presents the gait generation and navigation algorithms of an autonomous self-reconfiguring mobile robot platform, Chaser, which is capable of changing its configuration according to its surroundings. This robot attains selftransforming capability due to multiple degrees of freedom in its structure and the on-board range-sensing ability. The proposed gait generation and navigation algorithms enable Chaser to reconfigure itself to a shape that is best suited to pass through, over or under the obstacles presented to it. Moreover, the robot has the capability to traverse through various type of terrains by moving on wheels, walking like a quadruple and swimming like humans respectively. These multiple kinds of gaits have been coupled with a terrain navigation algorithm so that robot could identify different kinds of terrains and obstacles and transform itself to navigate seamlessly through them. The performance of Chaser is experientially tested with various real-world obstacles. Experimental results validate its performance.