Klub z Melbourne, którego pierwszy tytuł A-League w 2007 roku przypieczętował Archie Thompson, strzelając pięć goli w finale.
Domowym stadionem zespołu jest AAMI Park w Melbourne, otwarty w 2010 roku i mieszczący do 30 tysięcy widzów. Pierwszy mecz Victory na tym obiekcie rozegrano 10 maja 2010 roku jako mecz na cześć Kevina Muscata. W 2021 roku klub zdecydował, że od sezonu 2021/22 będzie rozgrywał tam wszystkie domowe mecze A-League, po latach korzystania również z Marvel Stadium.
Granat i duża biała litera V na piersi należą do charakterystycznych elementów domowego stroju. Litera nawiązuje do sportowej tradycji stanu Wiktoria i znajduje się także w klubowym herbie.
Melbourne Victory znalazło się wśród ośmiu zespołów ogłoszonych 1 listopada 2004 roku jako uczestnicy nowej A-League. Rozgrywki rozpoczęły się w 2005 roku, a pierwszy ligowy mecz Victory odbył się na Olympic Park.
18 lutego 2007 roku Victory wygrało swój pierwszy finał A-League, pokonując Adelaide United 6:0. Archie Thompson strzelił pięć goli, a Kristian Sarkies dołożył szóstego w doliczonym czasie. Zespół został pierwszym w historii ligi zdobywcą dubletu Premiership–Championship: wygrał zarówno sezon zasadniczy, jak i finał play-offów.
Thompson należał do inauguracyjnej kadry z sezonu 2005/06 i spędził w klubie jedenaście sezonów. Wywalczył z Victory trzy tytuły za sezon zasadniczy, trzy mistrzostwa rozstrzygane w finale oraz FFA Cup. Roddy Vargas, grający w Melbourne w latach 2006–2012, uczestniczył w zdobyciu dwóch mistrzostw i dwóch trofeów za sezon zasadniczy. Marco Rojas w sezonie 2012/13 zdobył Johnny Warren Medal oraz nagrodę dla najlepszego młodego piłkarza A-League, a w 2015 roku trafił do klubowej drużyny dekady.
W 2009 roku Victory ponownie pokonało Adelaide w finale, tym razem 1:0. Kolejne mistrzowskie finały wygrało w 2015 roku z Sydney FC 3:0 oraz w 2018 roku z Newcastle Jets 1:0. W 2015 roku na AAMI Park zwyciężyło też Perth Glory 2:0 w finale FFA Cup, później przemianowanego na Australia Cup.
Rywalizacja z Adelaide United nosi nazwę Original Rivalry i wyrasta także ze współzawodnictwa między stanami Wiktoria i Australia Południowa. Miejskie derby z Melbourne City zaczęły się po wejściu tego klubu do ligi w sezonie 2010/11, jeszcze pod nazwą Melbourne Heart.
