A method and device are disclosed from the perspective of a first UE (User Equipment) for changing sidelink identity for a sidelink unicast link associated with a second UE. In one method, the method includes the first UE establishing the sidelink unicast link with the second UE, wherein a first lower-layer identity of the first UE and a second lower-layer identity of the second UE are used for communicating between the first UE and the second UE via the sidelink unicast link. The method also includes the first UE transmitting a Link Identifier Update Request message to the second UE, wherein the Link Identifier Update Request message includes a new first lower-layer identity of the first UE or information for deriving the new first lower-layer identity. The method further includes the first UE receiving a Link Identifier Update Response message from the second UE. In addition, the method includes the first UE continuing to use the first lower-layer identity for receiving sidelink data from the second UE until a sidelink data frame with the new first lower-layer identity is received from the second UE.