Phenotypic plasticity is an evolutionary driving force in diverse biological processes, including the adaptive immune system, the development of neoplasms, and the bacterial acquisition of drug resistance. It is essential, therefore, to understand the evolutionary advantage of an allele that confers cells the ability to express a range of phenotypes. Of particular importance is to understand how this advantage of phenotypic plasticity depends on the degree of heritability of non-genetically encoded phenotypes between generations, which can induce irreversible evolutionary changes in the population. Here, we study the fate of a new mutation that allows the expression of multiple phenotypic states, introduced into a finite population otherwise composed of individuals who can express only a single phenotype. We analyze the fixation probability of such an allele as a function of the strength of inter-generational phenotypic heritability, called memory, the variance of expressible phenotypes, the rate of environmental changes, and the population size. We find that the fate of a phenotypically plastic allele depends fundamentally on the environmental regime. In a constant environment, the fixation probability of a plastic allele always increases with the degree of phenotypic memory. In periodically fluctuating environments, by contrast, there is an optimum phenotypic memory that maximizes the probability of the plastic allele’s fixation. This same optimum value of phenotypic memory also maximizes geometric mean fitness, in steady state. We interpret these results in the context of previous studies in an infinite-population framework. We also discuss the implications of our results for the design of therapies that can overcome resistance, in a variety of diseases.