Recently, it was shown that when reference frames are associated to quantum systems, the transformation laws between such quantum reference frames need to be modified to take into account the quantum and dynamical features of the reference frames. This led to a relational description of the phase space variables of the quantum system of which the quantum reference frames are part. While such transformations were shown to be symmetries of the system’s Hamiltonian, the question remained unanswered as to whether they enjoy a group structure, similar to that of the Galilei group relating classical reference frames in quantum mechanics. In this work (arXiv:2012.15769), we identify the canonical transformations on the phase space of the quantum systems comprising the quantum reference frames, and show that these transformations close a group structure defined by a Lie algebra, which is different from the usual Galilei algebra of quantum mechanics. We further find that the elements of this new algebra are in fact the building blocks of the quantum reference frames transformations previously identified, which we recover. Finally, we show how the transformations between classical reference frames described by the standard Galilei group symmetries can be obtained from the group of transformations between quantum reference frames by taking the zero limit of the parameter that governs the additional noncommutativity introduced by the quantum nature of inertial transformations.