Building wireless sensor networks based on the IEEE 802.15.4 standard is an interesting option, as the standard enables low-power, low data rate wireless communication. Many authors analyzed and optimized the operational phase of such networks. In contrast, the initial phase, containing the 802.15.4 association procedure, has mostly been neglected. In this paper, we therefore propose four optimization possibilities for the association procedure of a nonbeacon-enabled sensor network. Our results show that significant performance improvements in terms of association probability, speed, and energy consumptions can be achieved.