Techniques for performing network-assisted peer discovery to enable peer-to-peer (P2P) communication are described. In one design, a device registers with a network entity (e.g., a directory agent) so that the presence of the device and possibly other information about the device can be made known to the network entity. The network entity collects similar information from other devices. The device sends a request to the network entity, e.g., during or after registration. The request includes information used to match the device with other devices, e.g., information about service(s) provided by the device and/or service(s) requested by the device. The directory agent matches requests received from all devices, determines a match between the device and at least one other device, and sends a notification to perform peer discovery. The device performs peer discovery in response to receiving the notification from the network entity.