Flexible, or soft-shelled, eggs are almost unknown in the fossil record, leaving large gaps in our knowledge of the reproductive biology of many tetrapod clades. Here, we report two flexible-shelled eggs of the hyphalosaurid choristodere Hyphalosaurus baitaigouensis from the Early Cretaceous of China, one containing an embryo and the second associated with a neonate. Choristoderes are an enigmatic group of aquatic reptiles that survived the K-T extinction but died out in the Miocene. Hyphalosaurids, a specialized clade of Choristodera, resemble miniature plesiosaurs and are considered to be primarily aquatic in habit. Scanning electron microscopy of samples from the eggs reveals a thin, non-columnar external mineralized layer characterized by rounded nodes and tentatively identified poorly structured irregular pores, with an underlying amorphous layer presumably representing decomposed protein fibrils. While the relationships of Choristodera remain controversial, eggshell microstructure more closely resembles that of Lepidosauromorpha (the lineage including lizards) as opposed to that of Archosauromorpha (the lineage including birds and crocodiles).