Techniques for efficient and accurate frequency scans in Narrow Band-Internet of Things (NB-IoT) systems are provided. In an example, a user equipment (UE) searches for a cell on at least one of a plurality of frequency rasters based on a multi-stage search technique, wherein each stage of the multi-stage search searches the at least one frequency raster based on a different set of search parameters. The UE detects a cell on at least one of the frequency rasters based on the searching.