Wesley Mission Melbourne was established in 2001, following a review of the organisation known as Wesley Central Parish Mission. In February 2010, the organisation became known as Wesley Mission Victoria.
The name change from Wesley Central Parish Mission to Wesley Mission Melbourne was accompanied by administrative and structural changes. For example, from 2001, there was a Uniting Church Minister to the Mission to provide a continuing link between the Uniting Church, the Wesley Congregation in Lonsdale Street and Wesley Mission Melbourne.