Ancestral genomes are essential for studying the diversification of life from the last universal common ancestor to modern organisms. Methods have been proposed to infer ancestral gene order, but they lack scalability, limiting the depth to which gene neighbourhood evolution can be traced back. Here we introduce edgeHOG, a tool designed for accurate ancestral gene order inference with linear time complexity. We validated edgeHOG on various benchmarks and applied it to the entire OMA orthology database, encompassing 2,845 extant genomes across all domains of life. We reconstructed ancestral gene order for 1,133 ancestral genomes, including ancestral contigs for the last common ancestor of eukaryotes, dating back around 1.8 billion years, and observed significant functional association among neighbouring genes. EdgeHOG also dates gene adjacencies, allowing the detection of both conserved gene clusters and chromosomal rearrangements.