We discuss ways to enhance the location privacy of Bluetooth. The principal weakness of Bluetooth with respect to location privacy lies in its disclosure of a device’s permanent identifier, which makes location tracking easy. Bluetooth’s permanent identifier is often disclosed and it is also tightly integrated into lower layers of the Bluetooth stack, and hence susceptible to leakage. We survey known location privacy attacks against Bluetooth, generalize a lesser-known attack, and describe and quantify a more novel attack. The second of these attacks, which recovers a 28-bit identifier via the device’s frequency hop pattern, requires just a few packets and is practicable. Based on a realistic usage scenario, we develop an enhanced privacy framework with stronger unlinkability, using protected stateful pseudonyms and simple primitives.