Robotic vehicles are becoming increasingly attractive for non-destructive evaluation (NDE) of engineering structures, particularly for those areas where access is difficult or too hazardous for human intervention. This paper describes the design philosophy and prototype evaluation of a team of heterogeneous miniature climbing robots, which perform a range of NDE tasks, including magnetic flux leakage, eddy-current, visual and ultrasonic inspection. A host computer is used for overall supervision and inter-vehicle communication is achieved using wireless links. Each autonomous robot is located in 3D space by an ultrasonic positioning system in a listener-beacon configuration and is supplemented by data derived from optical wheel encoders and an on-board gyroscope. Results for non-contact ultrasonic inspection are presented, where the vehicle NDE payload comprises a pair of air coupled transducers, inclined at the appropriate angle to a test plate, for generation and reception of the A0 Lamb wave. C-scan images are shown, using the vehicle and the local positioning system to provide relative positional information