Evolution of systems whose Hamiltonians are generators of gauge transformations is a notion that requires more structure than the canonical theory provides. We identify and study this additional structure in the framework of relational observables (.partial observables.). We formulate necessary and sufficient conditions for the resulting evolution in the physical phase space to be a symplectomorphism. We give examples which satisfy those conditions and examples which do not. We point out that several classic positions in the literature on relational observables contain incomplete approach to the issue of evolution and false statements. Our work provides useful clarification and opens the door to studying correctly formulated definitions.