The technological demand to push the gigahertz (10(9) hertz) switching speed limit of today's magnetic memory and logic devices into the terahertz (10(12) hertz) regime underlies the entire field of spin-electronics and integrated multi-functional devices. This challenge is met by all-optical magnetic switching based on coherent spin manipulation. By analogy to femtosecond chemistry and photosynthetic dynamics--in which photoproducts of chemical and biochemical reactions can be influenced by creating suitable superpositions of molecular states--femtosecond-laser-excited coherence between electronic states can switch magnetic order by 'suddenly' breaking the delicate balance between competing phases of correlated materials: for example, manganites exhibiting colossal magneto-resistance suitable for applications. Here we show femtosecond (10(-15) seconds) photo-induced switching from antiferromagnetic to ferromagnetic ordering in Pr0.7Ca0.3MnO3, by observing the establishment (within about 120 femtoseconds) of a huge temperature-dependent magnetization with photo-excitation threshold behaviour absent in the optical reflectivity. The development of ferromagnetic correlations during the femtosecond laser pulse reveals an initial quantum coherent regime of magnetism, distinguished from the picosecond (10(-12) seconds) lattice-heating regime characterized by phase separation without threshold behaviour. Our simulations reproduce the nonlinear femtosecond spin generation and underpin fast quantum spin-flip fluctuations correlated with coherent superpositions of electronic states to initiate local ferromagnetic correlations. These results merge two fields, femtosecond magnetism in metals and band insulators, and non-equilibrium phase transitions of strongly correlated electrons, in which local interactions exceeding the kinetic energy produce a complex balance of competing orders.