We present a new Monte-Carlo algorithm to generate merger trees describing the formation history of dark matter halos. The algorithm is a modification of the algorithm of Cole et al (2000) used in the GALFORM semi-analytic galaxy formation model. As such, it is based on the Extended Press-Schechter theory and so should be applicable to hierarchical models with a wide range of power spectra and cosmological models. It is tuned to be in accurate agreement with the conditional mass functions found in the analysis of merger trees extracted from the LCDM Millennium N-body simulation. We present a comparison of its predictions not only with these conditional mass functions, but also with additional statistics of the Millennium Simulation halo merger histories. In all cases we find it to be in good agreement with the Millennium Simulation and thus it should prove to be a very useful tool for semi-analytic models of galaxy formation and for modelling hierarchical structure formation in general. We have made our merger tree generation code and code to navigate the trees available at http://star-www.dur.ac.uk/~cole/merger_trees . ; Comment: We thank Yu Lu for spotting errors in the appendix and helping identify an error in the coded algorithm. The (online) code and typos have been corrected. The fits and plots in the paper have been redone and match the (in press) MNRAS version