In this chapter I consider what recent work on background independent physics can do for structuralism, and what structuralism can do for background independent physics. I focus on the problems of time and observables in gravitational physics. The "frozen" character of the observables of general relativity is usually considered to constitute a serious problem for the theory. I argue that by invoking correlations between physical quantities we can provide a natural explanation of the appearance of time and change in timeless structures. I argue that this response can resolve a problem with Max Tegmark's "extreme structuralist" position. I then consider what bearing the mathematical representation used (namely Rovelli's framework of "partial" and "complete" observables) has on the debate over the nature of structure in discussions of structural realism (i.e. the question of how structures are to be conceived). I argue that it has both the resources to ground the notion of structure in physics and to answer the "no relations without relata" objection.