Some demonstrative embodiments include apparatuses, devices, systems and methods peer-to-peer connection session setup. For example, a first peer-to-peer device may set a waiting timer to count a waiting period during a connection session setup of a session with a second peer-to-peer device; and during the waiting period, check whether the second peer-to-peer device is in the connection session setup by transmitting a probe request to the second peer-to-peer device, the probe request including an Information (Info) attribute.