We present 65 optical spectra of the Type Ia supernova SN 2012fr, of which 33 were obtained before maximum light. At early times SN 2012fr shows clear evidence of a high-velocity feature (HVF) in the Si II 6355 line which can be cleanly decoupled from the lower velocity "photospheric" component. This Si II 6355 HVF fades by phase -5; subsequently, the photospheric component exhibits a very narrow velocity width and remains at a nearly constant velocity of v~12,000 km/s until at least 5 weeks after maximum brightness. The Ca II infrared (IR) triplet exhibits similar evidence for both a photospheric component at v~12,000 km/s with narrow line width and long velocity plateau, as well as a high-velocity component beginning at v~31,000 km/s two weeks before maximum. SN 2012fr resides on the border between the "shallow silicon" and "core-normal" subclasses in the Branch et al. (2009) classification scheme, and on the border between normal and "high-velocity" SNe Ia in the Wang et al. (2009a) system. Though it is a clear member of the "low velocity gradient" (LVG; Benetii et al., 2005) group of SNe Ia and exhibits a very slow light-curve decline, it shows key dissimilarities with the overluminous SN 1991T or SN 1999aa subclasses of SNe Ia. SN 2012fr represents a well-observed SN Ia at the luminous end of the normal SN Ia distribution, and a key transitional event between nominal spectroscopic subclasses of SNe Ia. ; Comment: 20 pages, 19 figures, version accepted by ApJ. Spectra now available from WISEREP or from http://www.mso.anu.edu.au/~mjc/SN2012fr/