The sudden appearance and potential lethality of severe acute respiratory syndrome associated coronavirus (SARS-CoV) in humans has focused attention on understanding its origins. Here, we assess phylogenetic relationships for the SARS-CoV lineage as well as the history of host-species shifts for SARS-CoV and other coronaviruses. We used a Bayesian phylogenetic inference approach with sliding window analyses of three SARS-CoV proteins: RNA dependent RNA polymerase (RDRP), nucleocapsid (N) and spike (S). Conservation of RDRP allowed us to use a set of Arteriviridae taxa to root the Coronaviridae phylogeny. We found strong evidence for a recombination breakpoint within SARS-CoV RDRP, based on different, well supported trees for a 5' fragment (supporting SARS-CoV as sister to a clade including all other coronaviruses) and a 3' fragment (supporting SARS-CoV as sister to group three avian coronaviruses). These different topologies are statistically significant: the optimal 5' tree could be rejected for the 3' region, and the optimal 3' tree could be rejected for the 5' region. We did not find statistical evidence for recombination in analyses of N and S, as there is little signal to differentiate among alternative trees. Comparison of phylogenetic trees for 11 known host-species and 36 coronaviruses, representing coronavirus groups 1-3 and SARS-CoV, based on N showed statistical incongruence indicating multiple host-species shifts for coronaviruses. Inference of host-species associations is highly sensitive to sampling and must be considered cautiously. However, current sampling suggests host-species shifts between mouse and rat, chicken and turkey, mammals and manx shearwater, and humans and other mammals. The sister relationship between avian coronaviruses and the 3' RDRP fragment of SARS-CoV suggests an additional host-species shift. Demonstration of recombination in the SARS-CoV lineage indicates its potential for rapid unpredictable change, a potentially important challenge for public health management and for drug and vaccine development.