The conceptual problems arising in the definition and measurement of temperature in non-equilibrium states are discussed in this paper in situations where the local-equilibrium hypothesis is no longer satisfactory. This is a necessary and urgent discussion because of the increasing interest in thermodynamic theories beyond local equilibrium, in computer simulations, in non-linear statistical mechanics, in new experiments, and in technological applications of nanoscale systems and material sciences. First, we briefly review the concept of temperature from the perspectives of equilibrium thermodynamics and statistical mechanics. Afterwards, we explore which of the equilibrium concepts may be extrapolated beyond local equilibrium and which of them should be modified, then we review several attempts to define temperature in non-equilibrium situations from macroscopic and microscopic bases. A wide review of proposals is offered on effective non-equilibrium temperatures and their application to ideal and real gases, electromagnetic radiation, nuclear collisions, granular systems, glasses, sheared fluids, amorphous semiconductors and turbulent fluids. The consistency between the different relativistic transformation laws for temperature is discussed in the new light gained from this perspective. A wide bibliography is provided in order to foster further research in this field.