Techniques to efficiently search for wireless networks while minimizing page loss are described. An available search time that excludes paging periods is determined. A search for cells in wireless networks is performed during the available search time. Pertinent information is obtained for cells acquired during the search. The pertinent information may be dependent on the type of search being performed. For a manual search to find detectable wireless networks, the pertinent information for each acquired cell may be network identifier information. For an automatic search to find higher priority wireless networks, the pertinent information for each acquired cell in a higher priority wireless network may be system information used to select that cell. The search may be suspended prior to a paging period. State information for the search may be saved prior to suspending the search. The search may be resumed using the saved state information at the end of the paging period.