Asymmetric segregation of key proteins at cell division—be it a beneficial or deleterious protein—is ubiquitous in unicellular organisms and often considered as an evolved trait to increase fitness in a stressed environment. Here, we provide a general framework to describe the evolutionary origin of this asymmetric segregation. We compute the population fitness as a function of the protein segregation asymmetry a, and show that the value of a which optimizes the population growth manifests a phase transition between symmetric and asymmetric partitioning phases. Surprisingly, the nature of phase transition is different for the case of beneficial proteins as opposed to deleterious proteins: a smooth (second order) transition from purely symmetric to asymmetric segregation is found in the former, while a sharp transition occurs in the latter. Our study elucidates the optimization problem faced by evolution in the context of protein segregation, and motivates further investigation of asymmetric protein segregation in biological systems.