The coacervation and complexation of oppositely charged polyelectrolytes are dependent on numerous environmental and preparatory factors, but temperature is often overlooked. Temperature effects remain unclear because the temperature dependence of both the dielectric constant and polymer-solvent interaction parameter can yield lower and/or upper critical solution phase behaviors for PECs. Further, secondary interactions, such as hydrogen bonding, can affect the temperature response of a PEC. That is, mixtures of oppositely charged polyelectrolytes can exhibit phase separation upon lowering and/or increasing the mixture's temperature. Here, the phase behavior of poly(diallylmethylammonium)/poly(acrylic acid) (PDADMA/PAA) complexes under varying KBr ionic strengths, mixing ratios, and temperatures at a fixed pH (in which PAA hydrogen bonding can occur) is examined. At room temperature, the PDADMA/PAA PECs exhibit four different phase states: precipitate, coexisting precipitate and coacervate, solid-like gel, and coacervate. Variable-temperature optical microscopy reveals the upper critical solution temperature (UCST) at which each phase transitioned to a solution state. Interestingly, the UCST value is highly dependent on the original phase of the PEC, in which solid-like precipitates exhibit higher UCST values. Large-scale all-atom molecular dynamics (MD) simulations support that precipitates exhibit kinetic trapping, which may contribute to the higher UCST values observed in the experiment. Taken together, this study highlights the significance of temperature on the phase behavior of PECs, which may play a larger role in stimuli-responsive materials, membraneless organelles, and separations applications.