Soft biometrics are biometric traits that do not offer exact human identification, however, they can provide adequate information to narrow-down the search space and give valuable insightsfor the subject in question. In this work, we examine the issues that emerge by analysing CCTV videos for soft biometrics and propose a methodology for extracting soft biometrics from low-quality and low-resolution video footage taken from real, street CCTV cameras. The proposed approach is based on the concept of Exemplars, that is, to find matches of the examined subject over a labelled dataset, which is able to encode the quality, colour and light variations of the surveillance images. Experiments have been conducted in a new challenging dataset that we introduce in this paper. It has been created using real CCTV footage, enhanced with a wide range of annotations from multiple people, and a manually created segmentation mask for each detection/person. This dataset is made available to scientific community for comparison and improvement of their methodologies in real-world scenarios.