This paper is directed towards developing a new fuzzy-logic based Ant Colony Optimization algorithm (FACO). The proposed algorithm takes into consideration the uncertainties that can be found in both the heuristic and the pheromone trails. This is achieved by representing the parameters of the problem and the metaheuristic algorithm as a pair of value and fuzzy level. The fuzzy level is considered as an indication of the uncertainty in the corresponding parameter. A stochastic-based technique is proposed to enable the artificial ant to choose the best incoming step based on the values of the probabilities and their corresponding fuzzy levels. The proposed FACO gives the optimal solution in a form of an optimal value and its corresponding fuzzy level. The proposed FACO is tested using the benchmark Quadratic Assignment Problem (QAP) and Travelling Salesman Problem (TSP). The results indicate that the developed FACO gives better optimal values with improved performance.