Originally inhabited by the Kurnai Aborigines, the area was explored by Angus McMillan in 1840. It was McMillan who named the Mitchell River on which the nearby land the township stands. Two years later Frederick Jones became the first European settler in the area when he settled at what is now known as Lucknow, using the land to breed horses for the Indian market. Archibald MacLeod was the first settler to take up land in the area now covered by the present town. Legend has it that he called his run "Bernisdale" after his birthplace on the Isle of Skye and that the name was changed to its present spelling when Macleod was surprised by the number of "bairns" which had appeared in the settlement and that the spelling was merely altered to fit local pronunciation. However the reality is that the Run was named Bairnsdale at it inception in March 1844 after a property at Gundaroo which belonged to his brother and then nephew both named Donald Macleod. Archibald Macleod had left this property to move his stock to Gippsland at the height of the drought that drove so many Monaro settlers further afield to find good pasture for their animals. The Gundaroo property was a 2000 acre grant of land given to Major Donald Macleod a Surgeon in the New South Wales Corp in the 1820s. The property at Gundarooo was on the Yass River north of Canberra and still existed in 2020. In the 1850s and 1860s the town grew as a result of its location on the Mitchell River and its access to the sea. It became a supply port for the East Gippsland goldfields until the railways were established later in the century. Goods were shipped into Lake King, up the Mitchell River to Bairnsdale then hauled overland, often by bullock teams. Ships were then loaded with cattle products and wool from the surrounding area for the return trip to Melbourne. The hops cultivated in the Mitchell Valley between 1868 and 1916 were also transported to Bairnsdale for shipment to the hop kilns. Some of the Hop Kilns still remained until recently on the eastern side of the Mitchell River. A bridge over the Mitchell River was commenced in 1870 and completed in 1875. A lift bridge was originally envisaged so that ships could continue along the Mitchell River to the original wharf near the centre of the town however the lift mechanism was defective and it was never used as a lift bridge. Newer wharves had already been developed below the new bridge. A post office was set up in 1856 and the township was surveyed and gazetted the following decade. A police station was established in 1862, a courthouse, school and post office were built six years later and the railway arrived in 1888. Barges conveyed wattle bark down the river to Jackson's tannery which commenced operations in 1876. A factory producing mining tools was opened the following year, an ice and butter plant in 1891, and a fruit cannery in 1907. Attempts were also made to develop an oil seed industry between 1890 and 1910. In 1920 the town experienced a riot as a result of a visit by the evangelist and tee-totaller, Tennyson Smith. Later in the decade immigrants from the south of Italy began to arrive and, as a consequence, the production of vegetables grew in importance throughout the region. Vegetable growing is still a major industry on the rich alluvial flats of the Mitchell river around Lindenow. In 1942 Bairnsdale won a national competition for providing the government with the largest war loan of any town its size. During the Second World War the RAAF also established a training centre in the area. The town itself, independent of the Shire, was not proclaimed until 1967. One of Bairnsdale's residents was the writer Hal Porter who spent much of his childhood in the town. He worked for a time on the Bairnsdale Advertiser and wrote of these experiences in his autobiography Watcher on the Cast-Iron Balcony. He returned many years later to work as a librarian and, in 1977, published a history of the town called Bairnsdale: Portrait of an Australian Country Town. Contemporary playwright, David Williamson, and NSW premier Jack Lang are two other memorable figures who passed some of their youth in Bairnsdale. Lang and poet Henry Lawson married the town's Bredt sisters. The Shire of Bairnsdale was first incorporated as a district in 1867, becoming a shire in 1869. On 31 May 1967, after a poll of ratepayers, the Centre Riding and parts of the East Riding severed to form the Town of Bairnsdale, which was proclaimed as a City on 14 July 1990. Bairnsdale remained unsubdivided and its 11 councillors governed the entire City. Its offices were at 8 Pearson Street, Bairnsdale. On 2 December 1994, the City was abolished, and merged with the Shires of Bairnsdale, Orbost, Tambo, most of Omeo and the Boole Boole Peninsula from Shire of Rosedale into the Shire of East Gippsland.
