A method, apparatus and computer program product are provided for facilitating efficient device discovery. In regards to a method implemented by a master device, a first identifier is received and stored. The method also receives a data packet comprising a second identifier from a particular device and determines whether at least a portion of the first identifier matches at least a portion of the second identifier. The method then, in an instant in which there is a match, causes a connection procedure to be initiated with the particular device. According to one example embodiment, the first identifier may be received from via a cloud service. According to another example embodiment, the first identifier may be received during an active data connection with another device. Corresponding apparatus and computer program products as employed by both master and slave devices are also provided.