Transformations between reference frames play a crucial role in our understanding of physical processes. In practice, reference frames are realised by physical systems, which are standardly treated as classical. However, assuming that every physical system is ultimately quantum, it is interesting to ask how a theory of transformations wrt quantum reference frames would look like, and what implications it would have for our description of spacetime. Recently, there has been a lot of effort towards developing a quantum generalisation of reference frame transformations, unveiling novel phenomena that are absent in the classical treatment of reference frames. Here, we develop a first-principles framework for quantum reference frame transformations which clarifies important conceptual issues of previous treatments. Based on the algebra of relative observables between a system and a reference frame, our operational perspective leads naturally to a mixed-state approach (incoherent twirling), in contrast to current pure-state approaches (coherent twirling). Within our framework, the full invariant quantum subsystem contains not only the algebra of relative observables between the system and the reference frame but also an â extra particle,â related to the invariant degrees of freedom of the reference frame itself. Importantly, this extra particle contains information about the â quantumnessâ of the reference frame and is essential to the unitarity of quantum reference frame transformations. Our approach is general, in the sense that it can be applied to a vast set of symmetry groups and to any type of system. We illustrate the physical meaning of the concepts developed by analysing quantum reference frame transformations with respect to the (centrally extended) Galilei group.