An electronic device is provided to include a user interface, a communication circuitry that supports Bluetooth (BT) communication and store a first BT address, a processor operatively connected with the user interface and the communication circuitry, and a memory operatively connected with the processor. The memory stores instructions that, when executed, cause the processor to establish a communication connection with a first external electronic device based on the first BT address, end the communication connection with the first external electronic device, receive a reconnection request based on the first BT address from the first external electronic device, transmit a communication connection request to the first external electronic device based on a second BT address different from the first BT address, using the communication circuitry in response to the reconnection request, and store information about whether the first external electronic device accepts or declines the communication connection request in the memory.