Gegründet wurde der Verein mit dem Namen Công an Hải Phòng als Polizeiverein von Hải Phòng, und er machte bis heute mehrere Namensänderungen durch. Die letzte war 2007, als der Verein sich in seinen jetzigen Namen Xi măng Hải Phòng umbenannte. Xi măng ist eine Marke des Zementherstellers Hải Phòng Zement, der Sponsor des Vereins ist. 2005/06 gelang der Aufstieg in die erste Liga und der Verein konnte auf Anhieb als Aufsteiger den 3. Platz feiern.
Einen spektakulären Neuzugang konnte der Verein im Juni 2009 vermelden. Der ehemals teuerste Spieler der Welt, der Brasilianer Denílson de Oliveira, wechselte von Itumbiara EC in die V-League zu Xi măng Hải Phòng.[1] Nach nur einem Spiel, in dem er auch ein Tor erzielen konnte, kündigte er seinen Vertrag auf.[2]
