Bei Einführung der A-League zur Saison 2005/06 wurde den acht ausgewählten Teams, darunter Melbourne Victory, für die folgenden fünf Jahre das Exklusivrecht in der jeweiligen Stadt eingeräumt. Angesichts des großen Zuschauerzuspruchs für Melbourne Victory, die den mit Abstand höchsten Zuschauerschnitt vorweisen, kamen frühzeitig Stimmen auf, die eine zweite A-League-Mannschaft für Melbourne für denkbar hielten.
Neben der Bewerbung eines Konsortiums um den Geschäftsmann Peter Sidwell, das unter dem Arbeitstitel Melbourne Heart stand, bewarben sich auch der Multimillionär Colin DeLutis[1] sowie der Verein South Melbourne FC[2] um eine zweite Melbourner A-League-Lizenz für die Saison 2010/11. Nachdem DeLutis wenige Monate vor der Vergabe-Entscheidung seine Bewerbung zurückgezogen hatte, war das Konsortium um Sidwell klarer Favorit für den Zuschlag, da die Football Federation Australia ethnisch neutrale Mannschaften bevorzugt, was die Chancen des griechisch geprägten South Melbourne FC schmälerte.[3]
Im September 2008 gab der australische Verband schließlich bekannt, dass man über eine Lizenzvergabe exklusiv mit dem Konsortium um Sidwell Gespräche führt,[4] im Juni 2009 wurde die Lizenz erteilt.[5]
Als Trainer wurde im Oktober 2009 der Niederländer John van ’t Schip präsentiert, und die Bekanntgabe der ersten Spielerverpflichtungen erfolgte Ende November 2009. 2012 wurde John Aloisi als neuer Trainer verpflichtet.[6]
Im Januar 2014 wurde der Klub zu 80 % von der City Football Group und zu 20 % von Melbourne Storm übernommen. Im Zuge dessen wurde der Klub am 5. Juni 2014 zu Melbourne City Football Club umbenannt und das Logo verändert.[7]
