Sustainable agriculture is essential for ensuring long-term food security and environmental health, as it addresses key challenges such as resource depletion, biodiversity loss, and climate change. To promote the adoption of sustainable agricultural practices, several initiatives have been introduced, offering economic incentives in exchange for compliance with sustainability policies. However, these new environmental regulations add complexity to long-term crop planning, further increasing the challenges associated with resource management and crop rotation constraints. As a result, farmers require decision-support tools to help them optimize their crop planning strategies while meeting sustainability requirements. In this paper, we present decision models and algorithms designed to assist farmers in solving multi-period crop rotation planning problems with sustainability constraints. In this setting, both the yield and profitability of a crop depend on the sequence of previous crops grown on the same plot of land, and the objective is to maximize farmers’ total profit. To address this challenge, we propose an arc-flow Integer Linear Programming model and a matheuristic algorithm, based on column generation, to efficiently solve the problem. Additionally, we analyze the complexity of the pricing problems and introduce an optimal dynamic programming algorithm for a special case. We evaluate our approach through an extensive experimental study using real-world data from Italian farms and incorporating the sustainability regulations of the European Union's Common Agricultural Policy. The numerical results demonstrate the effectiveness of our proposed methods in optimizing crop rotation planning while ensuring compliance with sustainability constraints. © 2025 The Authors