Complex coacervation is an emerging liquid/liquid phase separation (LLPS) phenomenon that behaves as a membrane-less organelle in living cells. Yet while one of the critical factors for complex coacervation is temperature, little analysis and research has been devoted to the temperature effect on complex coacervation. Here, we performed a complex coacervation of cationic protamine and multivalent anions (citrate and tripolyphosphate (TPP)). Both mixtures (i.e., protamine/citrate and protamine/TPP) underwent coacervation in an aqueous solution, while a mixture of protamine and sodium chloride did not. Interestingly, the complex coacervation of protamine and multivalent anions showed upper critical solution temperature (UCST) behavior, and the coacervation of protamine and multivalent anions was reversible with solution temperature changes. The large asymmetry in molecular weight between positively charged protamine (~4 kDa) and the multivalent anions (<0.4 kDa) and strong electrostatic interactions between positively charged guanidine residues in protamine and multivalent anions were likely to contribute to UCST behavior in this coacervation system.