A mobile communication device located within a radio signal coverage of a service network to serve as a relay User Equipment (UE) for Proximity-based Service (ProSe) UE-to-network relay is provided. The mobile communication device includes a wireless transceiver and a controller. The wireless transceiver performs wireless transmission and reception to and from the service network and a remote UE which is located out of the radio signal coverage of the service network. The controller transmits a Device-to-Device (D2D) Synchronization Signal (D2DSS) to the remote UE via the wireless transceiver in response to receiving a relay discovery message from the remote UE via the wireless transceiver, and requests radio resource allocation from the service network for the remote UE via the wireless transceiver in response to receiving a Direct Communication Request message from the remote UE via the wireless transceiver.