When?
Gymnosperm origins
Remember that the angiosperm flower is equivalent to a simple strobilus, or cone. It is essentially an axis that bears sporophylls. Angiosperms are unusual n that they often have bisporangiate (Latin, bis = two) flowers, meaning they produce both microsporangia and megasporangia in the same structure. Furthermore, their ovules are completely enclosed in the megasporophylls. Attempts to understand the origin of the flower from the perspective of the fossil record and/or morphology often try to hypothesize transformation series, or gradients of transitional structural states, that can be used to infer a connection between angiosperms and a known group of gymnosperms. Other approaches used genetics, or combinations of morphology and phylogenetics, to infer what the first flowers looked like.
Evidence from phylogeny
Evidence from structural botany
Bisporangiate cones are rare in other seed plants. Such cones are seen in some living gnetophytes (e.g., Ephedra, Gnetum) and in some extinct cycadeoids. In fact, the bisporangiate cone is one feature that has sometimes been used to in support of the hypothesis that angiosperms may be closely related to these gymnosperm groups (the so-called "Anthophyte Hypothesis"). The cones of gnetophytes and cycadeoids, however, are not structurally equivalent to the angiosperm flower. Gnetophytes, for example, have compound strobili, or cones in which the lateral structures are considered to have evolved from the modification of fertile branches. Thus, the gnetophyte cone is the equivalent of an angiosperm inflorescence, or a branching structure bearing a group of flowers. Attempts to infer the origin of the carpel from an extinct gymnosperm, such as the pteridosperm (seed fern) Caytonia, have proven contentious due to divergence in structural interpretations of the fossils representing these plants.
The earliest flowers
Estimation from phylogeny
In 2017, researchers used an extensive matrix of morphological characters on a topology of extant angiosperms and used sophisticated analytical techniques to reconstruction the likely ancestral character states for the ancestor to the crown-group angiosperm clade. They reconstruct the flower as bisexual (having both carpels and stamens); the perianth parts and stamens are whorled, whereas the carpels are helical in arrangement. All parts are floral structures are distinct and free (not fused to other floral parts). Overall, the reconstructed flower is fits within the rather variable floral structure seen in the basal angiosperms and Magnoliids.

Hypothesized reconstruction of the ancestral crown-group angiosperm. Reconstruction of the most recent common ancestor of all crown-group angiosperms based on morphological characters scored from modern angiosperm taxa. Credit: Fig. 1 in Sauquet et al. (2017, Nature Communications, CC BY 4.0).
Selected references & further reading
* Rothwell, G.W., W.L. Crepet, R.A. Stockey. 2009. Is the anthophyte hypothesis alive and well? New evidence from the reproductive structures of Bennettitales. American Journal of Botany 96: 296-322. https://doi.org/10/3732/ajb.0800209
* Sauquet, H., M. von Balthazar, S. Magallón, J.A. Doyle, P.K. Endress, E.J. Bailes, E. Barroso de Morais, K. Bull-Hereñu, L. Carrive, M. Chartier, G. Chomicki, M. Coiro, R. Cornette, J.H.L. El Ottra, C. Epicoco, C.S.P. Foster, F. Jabbour, A. Haevermans, T. Haevermans, R. Hernández, S.A. Little, S. Löfstrand, J.A. Luna, J. Massoni, S. Nadot, S. Pamperl, C. Prieu, E. Reyes, P. dos Santos, K.M. Schoonderwoerd, S. Sontag, A. Soulebeau, Y. Staedler, G.F. Tschan, A. W.-S. Leung, J. Schönenberger. 2017. The ancestral flower of angiosperms and its early diversification. Nature Communications 8:16047. https://doi.org/10.1038/ncomms16047