In this paper we describe AntHocNet, an algorithm for routing in mobile ad hoc networks based on ideas from the Nature-inspired Ant Colony Optimization framework. The algorithm consists of both reactive and proactive components. In a reactive path setup phase, multiple paths are built between the source and destination of a data session. Data are stochastically spread over the different paths, according to their estimated quality. During the course of the session, paths are continuously monitored and improved in a proactive way. Link failures are dealt with locally. The algorithm makes extensive use of ant-like mobile agents which sample full paths between source and destination nodes in a Monte Carlo fashion. We report results of simulation experiments in which we have studied the behavior of AntHocNet and AODV as a function of node mobility, terrain size and number of nodes. According to the observed results, AntHocNet outperforms AODV both in terms of end-to-end de-lay and delivery ratio.