We study a distributed user association algorithm for a heterogeneous wireless network with the objective of maximizing the sum of the utilities (on the received throughput)of wireless users. We consider a state-dependent wireless network where the rate achieved by the users are a function of their user associations as well as the state of the system. Also, we model the network to adapt its state based on the user associations. In this context, we present a completely uncoupled user association algorithm for utility maximization where the user's association is entirely a function of its past associations and its received throughput. In particular, the user is oblivious to the network state (and its evolution) as well as the association of the other users in the network. Using the theory of perturbed Markov chains [1], we show the optimality of our algorithm under appropriate scenarios. © 2017 IEEE.