Tolerance schemes of mechanical products are essential for product quality improvement and manufacturing cost reduction. High-reliability tolerance design relies on accurate error propagation analysis and extensive simulation experiments. However, high dimensionality and diversity of manufacturing errors and assembly errors caused by surface deformation significantly raise the complexity in balancing the effectiveness and efficiency of error propagation modeling. Therefore, a dynamic environmental adaptive-particle swarm optimization (DEA-PSO) framework for tolerance optimization based on multi-fidelity (MF) Co-Kriging surrogate model is proposed in this paper. The tolerance optimization problem is first mathematically formulated. To obtain an accurate prediction of assembly error, an MF model is constructed based on an integration of low-fidelity (LF) data obtained by continuous solid mechanics and asperity theory, and high-fidelity (HF) data computed by Finite Element Analysis (FEA). A hybrid-reward based adding point strategy is introduced to balance the exploration and exploitation and target the most promising regions for more efficient optimization. Additionally, a local perception strategy and a density-aware supplementary resampling method are proposed to promote the capability and robustness of global exploration. Finally, a case study of a machine tool slide component is conducted to validate the performance of the proposed method. Comparison with three existing methods showed the proposed method’s significant advantages in efficiency and effectiveness in tolerance optimization.