We present a real-time pedestrian detection system based on structure and appearance classification. We discuss several novel ideas that contribute to having low-false alarms and high detection rates, while at the same time achieving computational efficiency: (i) At the front end of our system we employ stereo to detect pedestrians in 3D range maps using template matching with a representative 3D shape model, and to classify other background objects in the scene such as buildings, trees and poles. The structure classification efficiently labels substantial amount of non-relevant image regions and guides the further computationally expensive process to focus on relatively small image parts; (ii)We improve the appearancebased classifiers based on HoG descriptors by performing template matching with 2D human shape contour fragments that results in improved localization and accuracy; (iii) We build a suite of classifiers tuned to specific distance ranges for optimized system performance. Our method is evaluated on publicly available datasets and is shown to match or exceed the performance of leading pedestrian detectors in terms of accuracy as well as achieving real-time computation (10 Hz), which makes it adequate for in-vehicle navigation platform.