A ultra wideband (UWB) wireless network may include a plurality of UWB wireless devices communicating over a plurality of UWB frequency bins extending over a UWB frequency range. At least one of the UWB wireless devices may be for determining a respective actual signal level associated with each UWB frequency bin, and generating a do-not-use UWB frequency bin list by comparing each actual signal level with at least one interference threshold. Thus, the UWB wireless devices can avoid using frequency bins experiencing excessive interference to thereby provide more reliable UWB communications.