In the present paper the step fixed charge transportation problem under uncertainty, particularly when variable and fixed cost are given in fuzzy forms, is formulated. In order to solve the problem, two metaheuristic, simulated annealing algorithm (SA) and variable neighborhood search (VNS), are developed for this NP-hard problem. Due to the significant role of parameters and operators on the algorithm’s quality, an extensive calibration in both SA and VNS is carried out with the aid of a set of experimental design. Through extensive computational experiments, appropriate parameter values of the proposed algorithms were chosen. For this purpose, twenty eight problems with different configuration have been generated at random and then the effectiveness of the proposed algorithms was evaluated using the relative percentage deviation (RPD) method.