Optimum conditions for the freeze-thaw stability (FTS) of mung bean starch (MBS) paste as a main ingredient in omija-eui were investigated. For the optimization of the paste preparation condition, the FTS of MBS prepared by boiling in a shaking water bath (BMSW) or by pressure-cooking in an autoclave (PCMA) were analyzed using a response surface methodology (RSM). In addition, the effects of various additives such as gums, sugars, and emulsifier were evaluated on the FTS of MBS paste prepared under optimal conditions. The predicted maximal FTS of MBS paste prepared by the PCMA method (73%) was higher than that of the paste prepared by the BMSW method (36%). In case of additives, gellan gum and sodium alginate effectively prevented the syneresis of MBS paste in the BMSW method and in the PCMA method, respectively. The use of a fructose fatty acid ester as an emulsifier decreased syneresis in a dose-dependent, while the addition of sugars accelerated syneresis. Consequently, MBS paste for omija-eui preparation may be efficiently prepared by adding sodium alginate and fructose fatty acid ester under the optimal conditions of 4.3% MBS content, $121^{circ}C$ heating temperature, and $89^{circ}C$ cooling temperature by pressure-cooking in an autoclave.