Wireless protocols in the unlicensed spectrum are developed for different requirements in terms of range and power, which makes them difficult to coexist in the same unlicensed spectrum. One such example is Zigbee and WiFi coexistence where low-power Zigbee nodes are frequently starved by WiFi nodes. Recent standardization efforts of short range IEEE 802.11af and long range IEEE 802.22 in the TV white spaces will make this problem more severe in the future. In this paper, we propose a novel PHY and MAC protocol for coexistence. Our protocol is decentralized and simple. The key building block is an adaptive preamble support at the PHY layer that allows high-power nodes to detect a low-power transmission even when the difference in transmit power constraints between the two groups of nodes is as high as 20dB. We show that this technique can prevent starvation of low-power nodes in almost all existing scenarios. We further propose a MAC protocol that builds on CSMA MAC and exploits the adaptive preambles functionality. We extensively evaluate our system in a test-bed and in simulations. We show that we can improve the data rates of low-power links by as much as 10x over existing MACs, without sacrificing more than 20%-40% of throughput of the rest of the system.