A memory structure disclosed in the present invention features a control gate and floating gates being positioned in recessed trenches. A method of fabricating the memory structure includes the steps of first providing a substrate having a first recessed trench. Then, a first gate dielectric layer is formed on the first recessed trench. A first conductive layer is formed on the first gate dielectric layer. After that, the first conductive layer is etched to form a spacer which functions as a floating gate on a sidewall of the first recessed trench. A second recessed trench is formed in a bottom of the first recessed trench. An inter-gate dielectric layer is formed on a surface of the spacer, a sidewall and a bottom of the second recessed trench. A second conductive layer formed to fill up the first and the second recessed trench.