 The Old Melbourne Gaol is a museum on Russell Street , in Melbourne , Victoria , Australia . It consists of a bluestone building and courtyard , and is located next to the old City Police Watch House and City Courts buildings . It was first constructed starting in 1839 , and during its operation as a prison between 1842 and 1929 , it held and executed some of Australia 's most notorious criminals , including bushranger Ned Kelly and serial killer Frederick Bailey Deeming . In total , 133 people were executed by hanging . Though it was used briefly during World War II , it formally ceased operating as a prison in 1924 ; with parts of the gaol being incorporated into the RMIT University , and the rest becoming a museum . 
