Changes in technologies and in consumer demands have made prior radio spectrum allocations far from efficient. To address this problem the FCC has recently reallocated spectrum for more flexible use in bands that are partially occupied by incumbent license holders. Often, it is necessary for the new license holder to relocate incumbents to make efficient use of the spectrum. Regulations structuring the negotiation between incumbent and new entrant can promote efficiency. In particular, giving the new entrant the right to move the incumbent with compensation can reduce negotiation costs and promote efficiency when there is private information about spectrum values but good public information about the cost of relocating the incumbent. We examine the experience of broadband PCS entrants in relocating microwave incumbents. We conclude with some remarks on how these ideas might be applied to digital television spectrum.