Gregory was born in 1819 at Farnsfield in Nottinghamshire, England - a date worth fixing clearly, since the careless can confuse him with his younger brother. He was barely ten when the family emigrated to the Swan River Colony in 1829, arriving in Western Australia only four months after the settlement itself was founded. He grew up in a struggling colony on poor soil, taking work where he could find it, for a while assisting a chemist, later surveying land alongside his brother Joshua. In December 1841 he joined the Government Survey Office. It was the perfect apprenticeship for what came next: he learned to read country, to measure it, and to move through it without waste - skills that would make him not the most famous of Australia's explorers, but arguably the most competent.

In 1855 the British government handed Gregory the most ambitious commission of his life: lead an expedition across the unmapped north of the continent. He took nineteen men, fifty horses, two hundred sheep, and the brilliant botanist Ferdinand von Mueller, and landed at the mouth of the Victoria River in the Northern Territory. Over the next fifteen months the party covered an astonishing distance - roughly 11,000 kilometres by sea and land - tracing the Victoria, following Sturt Creek in hope of an inland sea that dissolved instead into desert, then turning east across the Roper, the Leichhardt, and on toward Brisbane. On 2 July 1856 he blazed an inscription into a boab tree above the Victoria River, marking where he had buried a letter. That tree still stands. The expedition's true marvel, though, was its bookkeeping: Gregory brought every man home.

No European crossed this country alone, whatever the maps and monuments imply. On the northern expedition Gregory's party made first contact with the Gurindji people, for whom these strangers were the first Europeans ever seen. And when he set out to search for Leichhardt, Gregory depended on a bush guide named John Gilburri Fahy, a man who had lived thirteen years among the Aboriginal people of the Bunya Mountains and knew how to find water, read tracks, and move through country that would have killed a newcomer. Gregory secured Fahy's help with the promise of a pardon, which was granted in 1857. The blunt truth of inland exploration is that the explorers we celebrate survived because of the people whose knowledge they borrowed, hired, or extracted - and Fahy guided Gregory toward the very tree on the Barcoo that crowned the search.

Honours followed the achievements. The Royal Geographical Society awarded Gregory its Founder's Medal in 1857, and two years later, when Queensland separated from New South Wales to become its own colony, he was appointed its first Surveyor-General. He never explored again; he had no need to. From his office he shaped how the young colony understood and divided its land, and he built, by his own hands, a farmhouse called Rainworth in Brisbane. Later he sat for life in the Queensland Legislative Council and published, with his brother, the Journals of Australian Exploration. He was, in every sense, an establishment man by his fifties - but one whose authority rested on having actually crossed the ground he now governed on paper.

Gregory died on 25 June 1905 at Rainworth, and Brisbane turned out for him. An estimated 1,400 people filed past as his body lay in state at the Masonic Hall on Alice Street; hundreds more walked in the funeral procession to Toowong Cemetery. There he was buried on the northern slope of the hill, just below the grave of Sir Samuel Blackall, the governor for whom the Barcoo town was named - a final, fitting proximity for a man whose name is scattered across the map he helped draw. A national park, a highway, a river, and the boab Adansonia gregorii all carry his name. So does the country beyond the black stump that he once crossed and surveyed, and where, on a hot April day, he found a single carved letter waiting in the bark.