This paper examines optimal paddy-upland rotation systems, considering the trade-offs between economic, environmental, and food security indicators (crop revenues, nitrogen fertilizer inputs, and food calories, respectively). A regional optimization model targeted at a rich rice-producing region in Hokkaido, Japan was built for the analysis. It incorporates economic and food security objective functions to be maximized and an environmental objective function to be minimized under land-use constraints. A multi-objective genetic algorithm was applied to solve the multi-objective optimization problem at the regional level. Using k-means clustering, Pareto-optimal solutions were classified into three types of clusters: economic and food security, balanced, and environmental. The total crop revenue, total nitrogen fertilizer input, and total food calories were 11.5%, 4.8%, and 42.0% higher, respectively, for the economic and food security cluster than those for the environmental cluster. Considering the low nitrogen contamination in groundwater in the targeted region, the four-year paddy-upland rotation systems based on dry direct-seeded rice, spring wheat, soybeans, and direct- seeded sugar beets, which represent the highest adoption rate (83.9%) in the economic and food security cluster, should be promoted regionally to prioritize maximization of crop revenues and food calories. These findings are useful for local policymakers.