Maribor ima dolgoletno in bogato športno preteklost, ki je prepletena tudi s številnimi vrhunskimi dosežki v različnih športnih panogah. Med tistimi panogami, ki so pisale zgodovino mariborskega športa, je tudi ODBOJKA. Dobri poznavalci odbojke vedo, da je prav štajerska prestolnica zibelka tega športa v Sloveniji in da je tudi v nekdanji Jugoslaviji Maribor sodil med odbojkarska središča.
Prvi so v štajerski prestolnici odbojko začeli igrati telovadci Sokola Matica. Za nadaljni razvoj odbojke v mariboru je bilo izrednega pomena gostovanje češkoslovaškega prvaka Sokola Kromeriž leta 1930, kajti odbojka je bila v tej deželi že zelo razvita. Že leto pozneje je bilo v Mariboriu državno prvenstvo, na katerem so gostitelji slavili med naraščajniki in članicami.
Leta 1940 je bilo državno prvesntvo ponovno v Mariboru, domača moška in ženska vrsta sta postali najboljši v takratni kraljevini Jugioslaviji. Naslov so si priigrale Ljuba Copič, Danica Bertoncelj, Branka Kutin, Albina Herič, Anica Hiter, Breda Požar, Vida Ribarič, Ida Rižnar, Nada Mačus, Mira Stani, Vlada Skaza, Tončka Kikl, Mira Florjančič, Saša Mlaker, Milena Urbanek Tušak, Renata Jug Gorjup.
Obdobje po 2. Svetovni vojni, ko se je 1.SSK Maribor preimenoval v SŠD Polet, je bilo za mariborsko žensko odbojko zelo uspešno. Država se je spremenila, odbojkarske prvakinje pa so ostale iste. Po naslovu pravkinj leta 1946 so odbojakrice uspeh ponovile od nazivom MŠD Branik leta 1953. Po osvojitvi drugega naslova državnih prvakinj so se nekatere starejše in izkušenejše odbojkarice poslovile od aktivne športne poti, posledia tega pa so bili skromnejši dosežki na državnih prvenstvih, dokler nil eta 1968 ženska odbojkarske ekipa razpadla.
Toda krize je trajala le dve leti. Jeseni 1970 je bila spet ustanovljena ženska vrsta, za trenerja pa je bil izbran professor telesne vzgoje Edvard Dolinšek. Natančno delo z mladimi in obetavnimi odbojkaricami je iz leta v leto rojevalo sadove in leta 1980 je prva ženska članska ekipa po 21 letih spet zaigrala v jugoslovanski prvi zvezni ligi. Obdobje od leta 1980 do 1990 je bilo eno izmed najuspešnejših v zgodovini ženske ekipe, ki je leta 1982 nastopala pod imenom Paloma Branik. Vrhunec uspehov sta pomenila sezoni 1984/85 in 1985/86, saj je Paloma dvakrat zapored osvojila naslov državnih prvakinj. Ekipa Paloma Branik je v sezoni 1985/86 doživela tudi mednarodni krst, saj je prvič nastopila v evropskem pokalu državnih prvakinj; tekmi z vrsto CSKA iz Moskve je izgubila s 3:0. V sezoni 1989/90 je za ekipo prvič zaigrala tujka, in sicer Bolgarka Violeta Portokalska.
V samostojni Sloveniji je mariborska ženska odbojkarska ekipa osvojila kar 13 naslovov državnih pravkinj in se štirinajstkrat ovenčale z naslovom pokalnih prvakinj. Pri prvem naslovu je bil trener doctor Marko Zadražnik, v ekipi pa so bile Vesna in Petra Blažič, Mojca Voh Možič, Alenka Lešnik, Aleksandra Gosak, Nataša Prauhart, Natalija Pustoslemšek, Breda Ilešič, Edita Škerbinc in Jasmina Vrečko. Prvi prodor v ligo prvakinj je ekipi pod imenom Infond Branik uspel pod vodstvom profesorja Jurija Čopija. Njegov nalsednik Dragutin Baltič jo je popeljal do finala pokala Top Teams.
Petra Kramolc, Julija Obatnina, Ines Udrih, Andreja Vezjak, Anja Cvirn, Loredana Voichita Cristea, Hajdi Hauptman, Maja Ilić, Sonja Borovinšek, Jasmina Vugdalić, Urša Podlesnik, Andreja Radivoj in Nuša Draškovič so imena igralk, ki na prehodu v 21. stoletje na domačih tleh niso poznale poraza.
Ime kluba skozi zgodovino v samostojni Sloveniji:
1991/1994 Paloma Branik
1995/2000 Infond Branik
2000/ Nova KBM Branik
Nova KBM d.d. je sponzor kluba skozi vso samostojno Slovenijo, kot generalni sponzor pa klub podpira od leta 2000, ko je klub spremenil ime v Odbojkarski klub Nova KBM Branik.
Uspehi v samostojni Sloveniji:
Državni prvaki:13-krat
1991/92, 1992/93, 1995/96, 1997/98, 1998/99, 1999/00, 2000/01, 2001/02, 2008/09, 2010/11, 2011/12, 2012/13, 2013/14
Pokalni zmagovalci:14-krat
1991/92, 1992/93, 1993/94, 1995/96, 1997/98, 1998/99, 1999/2000, 2000/01, 2001/02, 2002/2003, 2009/10, 2010/11, 2011/12, 2014/15
Prvaki srednjeevropske lige: 3-krat
2009/10, 2011/12, 2012/13