The demand for Internet connectivity has grown exponentially in the past few years. Moreover, the advent of new services such as Voice over IP (VoIP), Video on Demand (VOD) and Videoconferencing applications have caused a sever increase in traffic, which makes it extremely hard to ensure an acceptable level of quality. This is mainly attributed to current routing strategies, such as Link State (LS) and Distance Vector (DV), which are not optimal in terms of Quality of Service (QoS). This paper presents a QoS-Aware routing strategy based on the Ant Colony Optimization (ACO) concept, where a set of artificial ants are used to determine the optimal path. The proposed method was compared to other state of the art ACO procedures and traditional routing schemes like LS and DV. Simulation results clearly demonstrate that the proposed scheme outperforms all the methods considered in this paper where throughput gains of 8% and a reduction in delay of 38% for time critical applications were achieved.