There is provided a communication device, comprising, a communication unit which mediates a communication connection with another communication device, a memory unit which stores connection history information which indicates history of a connection party connected via the communication unit and connection restriction information to limit the number of connection party changes, and a determination unit which determines connection acceptability with a new connection party based on the connection history information and the connection restriction information stored in the memory unit.