Some demonstrative embodiments include apparatuses, systems and/or methods of discovering a wireless communication device. For example, a first wireless device may include a radio to communicate over a wireless communication medium according to a discovery scheme including a plurality of contention-based discovery windows (DWs), the radio to communicate with a second wireless device a discovery frame during a first discovery process, the discovery frame including an indication of one or more selected DWs of the plurality of DWs; and a controller to switch the first wireless device between a power save state and an active state, the controller to switch the first wireless device to operate in the active state in the one or more selected discovery windows to discover the second wireless device during a second discovery process, subsequent to the first discovery process.