A robust multi-fidelity optimization method for micro Mars entry probe design is presented in this paper. In the robust design, aerodynamic and atmospheric model are assumed to be affected by epistemic uncertainties (partial or complete lack of knowledge). Evidence Theory is employed to quantify the uncertainties, and formulate the robust design into a multi-objective optimization problem. The optimization objectives are set to minimize interior temperature of Thermal Protection Systems (TPS), while maximize its belief value under uncertainty. A population based Multi-objective Estimation of Distribution Algorithm (MOEDA) is designed for searching robust Pareto front. In this algorithm, affinitive propagation clustering method divides adaptively the population into clusters. In each cluster, local Principal Component Analysis (PCA) is adopted for estimation of distribution, and reproducing individuals. Variable-fidelity aerodynamic model management is integrated into the robust optimizations. The fidelity management model uses analytical aerodynamic model first to initialize the optimization searching direction. With the development of the optimization, more data from high-accuracy model (CFD) are put into aerodynamic database. Artificial Neural Network (ANN) based surrogate model is used for reducing the computational cost. Finally, an application of the proposed optimization strategy for a micro probe with diameter no more than 0.8 meter is presented.