As a dedicated communication protocol for Internet-of-Things, narrowband internet of things (NB-IoT) needs to establish the communication link rapidly and reduce retransmissions as much as possible to achieve low power consumption and stable performance. To achieve these targets, the low-power scheme of the initial cell search and frequency tracking is investigated in this paper. The cell search process can be subdivided into narrowband primary synchronization signal (NPSS) detection and narrowband secondary synchronization signal (NSSS) detection. We present an NPSS detection method whose timing metric is composed of symbol-wise autocorrelation and a dedicated normalization factor. After the detection of NPSS, the symbol timing and fractional frequency offset estimation is implemented in a resource-efficient way. NSSS detection is conducted in the frequency domain with a calculation-reduced algorithm based on the features of NSSS sequences. To compensate the accumulated frequency offset during uplink transmission, a pilot-aided rapid frequency tracking algorithm is proposed. The simulation results of the proposed cell search scheme are outstanding in both normal coverage and extended coverage NB-IoT scenarios, and the accumulated frequency offset can be estimated with high efficiency.