A secure wireless communication link (pairing) between two devices can be established using cleartext wireless transmissions between devices not joined to a network (“probes”). One device can broadcast a first probe indicating that it is seeking to establish a pairing. The other device can respond with a second probe, and the two devices can establish a shared secret, e.g., by exchanging further information using additional probes. Thereafter, either device can send a message to the other by encrypting the message using a cryptographic key derived from the shared secret; encrypted messages can also be sent within probes. The receiving device can extract an encrypted message from a probe and decrypt it using the cryptographic key. The encrypted message can include credentials usable by the receiving device to join a wireless network.