Symmetries are defined in histories-based theories, paying special attention to the class of history theories admitting quasi-temporal structure (a generalization of the concept of temporal sequences'' of events'' using partial semigroups) and logic structure for single-time histories.'' Symmetries are classified into orthochronous (those preserving the temporal order'' of events) and nonorthochronous. A straightforward criterion for the physical equivalence of histories is formulated in terms of orthochronous symmetries; this criterion covers various notions of physical equivalence of histories considered by Gell-Mann and Hartle (1990, in ``Complexity, Entropy, and the Physics of Information'' (W. Zurek, Ed.), SFI Studies in the Science of Complexity, Vol. 8, p. 425, Addison Wesley, Reading, MA) as special cases. In familiar situations, a reciprocal relationship between traditional symmetries (Wigner symmetries in quantum mechanics and Borel-measurable transformations of phase space in classical mechanics) and symmetries defined in this work is established. In a restricted class of theories, definition of a conservation law is given in the history language which agrees with the standard ones in familiar situations; in a smaller subclass of theories, a Noether-type theorem (implying a connection between continuous symmetries of dynamics and conservation laws) is proved. The formalism evolved is applied to histories (of particles, fields, or more general objects) in general curved spacetimes. Sharpening the definition of symmetry so as to include a continuity requirement, it is shown that a symmetry in our formalism implies a conformal isometry of the spacetime metric. 2001 Academic Press Contents. I. Introduction. II. Histories-based generalized quantum mechanics. A. More about partial semigroups. B. The augmented temporal logic formalism. III. Symmetries in histories-based generalized quantum mechanics. A. Symmetries in the Houtappel et al. approach. B. Symmetries in the augmented temporal logic formalism. C. Symmetries in general quasitemporal theories and in Isham Linden type theories. IV. Traditional vs. temporal logic descriptions of symmetries in nonrelativistic quantum mechanics. A. The HPO formalism. B. Symmetries in traditional quantum mechanics in the HPO formalism. C. Recovering Wigner symmetries from those in the temporal logic formalism. V. Traditional vs. temporal logic descriptions of symmetries in classical mechanics. VI. Physical equivalence of histories.