Highway agencies encounter the challenge of limited financial resources while striving to improve the condition of their road networks. As a result, optimization models are increasingly used to schedule pavement maintenance and rehabilitation activities under budget constraints. Previous probabilistic optimization models have primarily focused on incorporating uncertainty in budget constraints, often neglecting other sources of uncertainty. In particular, the failure to account for uncertainties in future pavement condition and maintenance effectiveness within multi-year optimization models may lead to mistimed maintenance interventions, ultimately yielding suboptimal schedules. Hence, this paper introduces a stochastic preventive maintenance optimization model that considers uncertainties in deterioration and improvement of pavement condition, together with budget constraints. The model aims to minimize lifecycle costs while maximizing road network condition. To solve this complex problem, the study employs a Multi-objective Genetic Algorithm (MOGA), known for its robust search capabilities in determining optimal global solutions. To mitigate the computational complexity of the stochastic MOGA model, three approaches are implemented: (1) identifying and incorporating the most used maintenance alternatives, (2) grouping pavement sections by age, and (3) introducing a filtering constraint that imposes a rest period following treatment applications. The results demonstrate that the Pareto optimal solutions are significantly influenced by varying levels of uncertainty in pavement condition deterioration and improvement. The developed stochastic MOGA model provides highway agencies and decision-makers with probabilistic Pareto optimal solutions that account for multiple sources of uncertainty. These solutions can be employed to select maintenance schedules that align with different risk thresholds and certainty levels.