We study in detail the issue of gauge-fixing in theories with one universal extra dimension, i.e. theories where both bosons and fermions display Kaluza-Klein (KK) excitations. The extra dimension is compactified using the standard orbifold construction for a massless chiral fermion. We carry out the gauge-fixing procedure at the level of the five-dimensional theory and determine the tree-level propagators and interaction vertices needed for performing perturbative calculations with the effective four-dimensional theory resulting after the compactification. The gauge-independence of the tree-level S-matrix involving massive KK modes is verified using specific examples. In order to obtain massive fermionic zero modes one has to enlarge the theory by introducing a set of mirror fermions, a construction which is carried out in detail. Finally, the gauge-independence of the tree-level S-matrix involving the resulting new mass-eigenstates is proved by resorting to generalized current conservation equations.