Embodiments of a system and method for secure discovery and identification of devices via a wireless network are generally described herein. In some embodiments a wireless device may transmit an anonymous ephemeral identifier that may be utilized by a second device to determine, by accessing a provider or social network, whether the private identity masked by the ephemeral identifier is known to the user of the second device. In some embodiments a provider may receive user or device registrations; maintain a record of private identifiers, ephemeral identifiers, and known user data for a plurality of users; and access one or more social networks to acquire known user data. The ephemeral identifiers may be periodically updated by the provider. In some embodiments a discovery module in a plurality of devices may automatically establish a communication connection between devices in response to a previously established relationship between users of the respective devices.