The Classical Transportation Problem (TP) Tableau which utilizes continuous variable cost has been used to model and solve distribution problems. However, many real distribution problem decisions which require various combination of fixed and variable cost and having several mixed variables of the binary integers and continuous types make this approach limited. This challenge requires new integrated models that are also NP hard for which exact algorithms such as Branch and bound, cutting plane algorithm may be inefficient to use as the problem size increases in practical business cases. We present in this paper, an integrated model of Facility Location (FL) and Step Fixed charge Transportation Problem (SFCTP). This problem is solved using a solution heuristic that utilizes relaxation and linearization approach to recast it to the classical TP as a starting solution. For the improved solution, a low cost and efficient perturbation heuristic that works in a row-wise manner is developed. We also propose a lower bound based on literature as a guide in achieving a solution. Lastly, a numerical example is presented to illustrate the procedures of the solution.