The interplay between topology and dynamics in complex networks is a fundamental but mostly unexplored problem. Here we study this phenomenon for a variable following extremal dynamics on a network which is in turn shaped by the variable itself. Each vertex is assigned a fitness, and the vertex with minimum fitness and its neighbours are updated as in the Bak--Sneppen model. On the other hand, the links are determined by the vertices' variables as in the fitness network model. We show analytically and numerically that the system self--organizes to a nontrivial state which differs from what is obtained when the two processes are decoupled. A power--law decay of dynamical and topological quantities above a threshold emerges spontaneously, as well as a feedback between different dynamical regimes and the underlying network's correlation and percolation properties.