This paper addresses a novel sustainable hub location problem (SHLP) in which two new environmental-based cost functions accounting for air and noise pollution of vehicles are incorporated. To cope with uncertain data incorporated in the model, a mixed possibilistic–stochastic programming approach is proposed to construct the crisp counterpart. A simulated annealing (SA) and an imperialist competitive algorithm (ICA) with a new solution representation are developed to solve real-sized instances whose performances are compared with a proposed lower bound. Finally, some computational experiments are provided to demonstrate the effectiveness of the proposed model and solution approaches.