The future generation of computer networks brings us several challenges. Automation is one of the most pursued functionalities for such networks. It means that research around this area goes toward the auto- and self- technologies such as self-management, self-addressing and self-healing. This paper presents a novel approach for self-addressing in dynamic networks. It is a stateful and distributed protocol, which relies on addressing servers spread in the network. These servers have the objective of executing addressing tasks, aiming an address conflict-free environment. We also present the results of the first experiments on the proposed approach, where its performance and behavior were evaluated. To validate these results, comparisons between our proposed protocol and a classic stateless addressing mechanism were done.