We introduce ACOPHY, a novel framework to apply Ant Colony Optimization (ACO) for phylogenetic reconstruction. ACOPHY overcomes a main drawback of other attempts to reconstruct phylogenies by defining a compact ACO graph that is nicely coupled with the tree space. The proposed graph allows the ants to walk globally through the tree space. Thus, ACOPHY can be generally applied to all well-known optimality criteria in phylogenetics. We compared ACOPHY with the traditional phylogenetic method PHYLIP and obtained slightly better results. This is promising since our current implementation of ACOPHY is still at the proof of concept stage. We list a number of points where ACOPHY can be improved. Once the improvements are integrated, we hope for competitive performance against other recent phylogenetic inference methods.