Contractile actomyosin bundles, stress fibers, govern key cellular processes including migration, adhesion, and mechanosensing. Stress fibers are thus critical for developmental morphogenesis. The most prominent actomyosin bundles, ventral stress fibers, are generated through coalescence of pre-existing stress fiber precursors. However, whether stress fibers can assemble through other mechanisms has remained elusive. We report that stress fibers can also form without requirement of pre-existing actomyosin bundles. These structures, which we named cortical stress fibers, are embedded in the cell cortex and assemble preferentially underneath the nucleus. In this process, non-muscle myosin II pulses orchestrate the reorganization of cortical actin meshwork into regular bundles, which promote reinforcement of nascent focal adhesions, and subsequent stabilization of the cortical stress fibers. These results identify a new mechanism by which stress fibers can be generated de novo from the actin cortex and establish role for stochastic myosin pulses in the assembly of functional actomyosin bundles.