Petal patterns contribute to the reproductive success of flowering plants by attracting pollinators and protecting reproductive organs from environmental factors. While some transcription factors (TFs) controlling pigment production and cuticle elaboration have been identified, little is known about the upstream developmental processes that first establish the petal regions where these regulators are active-the pre-patterning phase. Here, we developed a computational model of the evolution and development of petal patterns. We selected for gene regulatory networks (GRNs) that could generate the proximo-distal bullseye pattern of Hibiscus trionum petals, which resulted in robust patterning dynamics and a variety of bullseye proportions. We found that the evolution of these bullseye patterns was often accompanied by the spontaneous emergence of a third cell type at the boundary between the proximal and distal regions with a unique gene expression profile. These bullseye boundary cells appeared in the majority of simulations despite not being explicitly selected for, and we validated their presence experimentally in H. trionum petals. Although boundary cell types could emerge spontaneously without apparent function, our results indicate they were more often important for pattern formation and more evolutionarily stable when gene expression was noisy. This suggests that this emergent cell type contributes to reproducible bullseye formation by buffering against developmental variability. Altogether, these results illuminate the early steps of petal pattern formation and demonstrate how novel cell types arising spontaneously and repeatedly from selection on other features can help achieve developmental robustness.