Mihajlicsenko pályafutását a Gyinamo Kijev serdülőcsapatában kezdte. A szovjet élvonalban1981-ben mutatkozott be, és csapatával még ebben az idényben szovjet bajnoki címet ünnepelt. A Gyinamo Kijevben töltött 9 év alatt négy bajnoki címet és három szovjetkupa-győzelmet szerzett, 1986-ban KEK-győztes, később két alkalommal választották a szovjet élvonal legjobb ukrán labdarúgójának, egyszer pedig elnyerte az Év Szovjet Labdarúgója-címet is.
1990-ben Olaszországba, az Sampdoria csapatához igazolt. Bemutatkozása ismét sikeres volt: a Mihajlicsenkót is a soraiban tudó genovai alakulat története első olasz bajnoki címét szerezte. Mihajlicsenko 24 mérkőzésen szerzett 3 góllal járult hozzá a történelmi sikerhez.
Az 1991–1992-es szezont már Skóciában, a Rangers csapatával kezdte meg, és bemutatkozó idényében újfent bajnoki címet szerzett. A Glasgowban töltött öt évad során minden alkalommal skót bajnoki címhez segítette csapatát, három alkalommal pedig skótkupa-győzelmet ünnepelt.
Labdarúgó-pályafutását 1997-ben fejezte be.
Rangers
Sampdoria
Gyinamo Kijev
.svg){kind=small}
