The first inhabitants of the area were Indigenous Australian tribes, specifically the Jawoyn people and Wardaman people. It was important meeting place for these tribes and remains a place of convergence.
Explorer John McDouall Stuart passed through the area in 1862 on his successful sixth journey across the continent from north to south. On 4 July 1862, Stuart crossed the Katherine River (90 km upstream from the present town) and recorded in his diary: "Came upon another large creek, having a running stream to the south of west and coming from the north of east. This I have named 'Katherine', in honour of the second daughter of pastoralist James Chambers Esq." There is some conjecture over Stuart's accuracy. Chambers's wife's name was Katherine but, according to most sources, his daughter's name was Catherine.
Katherine Telegraph Station was established on 22 August 1872 and the completion of the Overland Telegraph Line later in 1872, and the town began with a small permanent population on the west side of the Katherine River. Katherine benefited from the proximity to nearby gold fields including Pine Creek 90 kilometres to the north.
Gold was discovered 50 kilometres to the north in 1889 at Mount Todd.
The North Australia Railway was extended to Katherine with construction beginning in 1923 of the Katherine railway bridge. During construction of the railway, the town's centre was relocated to the eastern side of the river. The bridge was completed in 1926 and the first train crossed on 21 January 1926. In 15 July 1926, the town's present site was gazetted. The original post office and the Overland Telegraph station were set just above Knott's Crossing and next to the Sportsman's Arms Hotel that had quarters for the station master at the Overland Telegraph station and a single room police station.
During World War II, the Australian Army set up two hospitals around Katherine, the 101st Australian General Hospital and 121st
