Early screening in Colorectal Cancer consists in finding and removing small precancerous masses or neoplastic lesions developed from the mucosa, usually lesions smaller than 10 mm. Localization of small neoplastic lesions is a very challenging task since colon exploration is highly dependent on the expert training and colon preparation. Several strategies have attempted to locate neoplasias, but usually they are huge lesions that a trained gastroenterologist could hardly miss. This work presents a saliency-based strategy to localize polypoid and non-polypoid neoplastic lesions smaller than 10 mm in colonoscopy videos by combining spatio-temporal descriptors. For doing so, a per-frame-multi-scale representation is computed and edge, texture and motion features are extracted. Each of these features is used to construct a primary saliency map which are then combined to obtain a coarse saliency map. Finally, the neoplasia is localized as the bounding box of a circular region, approximated by the Hough transform, with the largest salience. The proposed approach was evaluated in 8 short colonoscopy videos obtaining an average of Annotated Area Covered of 0.75 and a precision of 0.82.