The present work discusses a novel conceptual formulation of the Fractional-Order Ant Colony Algorithm (FACA), which is a fractional long term memory based cooperative learning approach. In the standard Integer-order Ant Colony Algorithms (IACAs), each ant selects its next edge on the graph according to a transition probability that is obtained from the pheromone value and additional information found on the edges adjacent to its present node. To improve the optimization capability associated with traditional IACAs, we have studied here, as an interesting theoretical problem, whether it will be possible to apply the inherent strengths of fractional calculus to modify the transition behaviour of the classical IACAs by replacing the simple one-step probability by a more complex expression that seems to include some look-ahead information. The formal motivation for this expression is from the fractional derivatives where simple differences are replaced by more involved expressions. Motivated by this need, in this work, we introduce a novel algorithm called Fractional-Order Ant Colony Algorithm (FACA). At first, we extend the IACA to the FACA based on the long-term memory of fractional difference. Secondly, we discuss the algorithmic flow of the FACA. Thirdly, we present the mathematical proof and convergence analysis of the FACA. Fourthly, we present the experiment results obtained and the associated analyses carried out. The paper introduces a novel mathematical approach, fractional calculus, to the family of ant colony algorithms, that differs from most of the previous approaches and hence it presents an interesting theoretical contribution in this research domain.