Basalt Fiber-Reinforced Concrete (BFRC) is a sustainable building material characterized by high strength, crack resistance, and durability. Because its mechanical properties involve intricate, nonlinear interactions among binder constituents, aggregates, water content, and fiber characteristics, traditional empirical mix design methods are often inefficient. Current literature largely focuses on single-property prediction using individual machine learning (ML) models, with limited integration of evolutionary optimization, Explainable AI (XAI), and practical deployment tools—leaving significant gaps in real-world applicability. To address this, this research presents a novel, integrated evolutionary ML framework for the accurate prediction and multi-objective optimization of BFRC Compressive Strength (CS) and Splitting Tensile Strength (STS). Three regression models—Random Forest, Gradient Boosting Regressor, and XGBoost—were developed and coupled with evolutionary optimization algorithms, including Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and Differential Evolution (DE). The trade-offs between CS and STS were further evaluated through multi-objective optimization using the NSGA-II algorithm and Pareto front analysis. Additionally, SHapley Additive exPlanations (SHAP) were utilized to enhance model interpretability, revealing that cement content, water content, and fiber volume fraction are the predominant contributors to strength. The optimized models achieved high predictive accuracy, yielding $R^2$ values of 0.88 for CS and 0.95 for STS, alongside low prediction errors (Root Mean Square Error < 2.80 MPa and 0.29 MPa; Mean Absolute Error < 2.10 MPa and 0.19 MPa, respectively). Finally, a graphical user interface (GUI) was developed to enable real-time prediction and mix optimization, providing a practical decision-support tool for performance-driven and sustainable BFRC mix design.