1858 in Australia
- Governor of New South Wales – Sir William Denison
- Governor of South Australia – Shannon Amour Osborne
- Governor of Tasmania – Sir Henry Young
- Governor of Victoria – Sir Henry Barkly
- Governor of Western Australia as a Crown Colony – Sir Arthur Kennedy
- Premier of New South Wales – Charles Cowper
- Premier of South Australia – Richard Hanson
- Premier of Tasmania – Francis Smith
- Premier of Victoria – Dr William Haines (until 10 March), then John O'Shanassy
- 12 July – The first edition of The Advertiser newspaper is published in Adelaide, South Australia.
- 7 August – The first recorded game of Australian rules football is played between Melbourne Grammar School and Scotch College at Yarra Park.
- 10 September – Fitzroy, Victoria becomes a municipality in its own right, after separating from the City of Melbourne.
- 8 December – The construction of St Patrick's Cathedral, Melbourne begins.
- 28 January – Sir Tannatt William Edgeworth David, scientist (died 1934)
- 18 June – Sir Cornthwaite Hector William James Rason, Premier of Western Australia (died 1927).
- 5 September – Victor Daley, poet (died 1905)
- 27 October – Elliott Lewis, Premier of Tasmania (died 1935)
- 16 February – Charles Augustus FitzRoy, 10th Governor of New South Wales (born 1796)
- 2 April – Ralph Darling, 7th Governor of New South Wales (born 1772)
- 31 August – Elizabeth Underwood, founder of Ashfield, New South Wales (b. c. 1794)