 An allotment of scrubland to the north @-@ east of Melbourne was selected as Port Phillips first permanent gaol . On 1 January 1838 , George Wintle was appointed to be gaoler at the prison at £ 100 a year ; with the site becoming colloquially known as Wintle 's Hotel . Construction of the gaol started in 1839 – 1840 on Collins Street West , but it was considered too small at the time . A second gaol was then built between 1841 and 1844 at the corner of Russell and La Trobe Streets , adjoining the then Supreme court . The first cell block was opened for prisoners in 1845 , but the facilities were considered inadequate ; escapes occurring frequently . The gaol was already crowded by 1850 . 
