Czasy pionierskie
W piłkę siatkową w Międzyrzeczu zaczęto regularnie grywać w 1949, gdy - z inicjatywy Jana Kocaja - doszło do wybudowania do Obrzycach (wschodniej części miasta) pierwszego boiska dla potrzeb tej dyscypliny. Trzy lata później przy tamtejszym szpitalu utworzono pierwszy męski zespół siatkarski w "grodzie nad Obrą", który od razu przystąpił do zmagań o Puchar CRZZ. W 1955 nadano mu nazwę KS Zdrowie, a dzięki wywalczeniu - w tym samym czasie - Pucharu CRZZ na szczeblu województwa zielonogórskiego, został on zgłoszony do rozgrywek ligowych (klasy A). Z niezłymi wynikami występował na szczeblu regionalnym (klasa A i liga okręgowa) do 1959, gdy z przyczyn finansowych został rozwiązany. Rok później powstała w Obrzycach - TKKF Astoria, której skład w większości stanowili byli zawodnicy "Zdrowia". Niemal od razu stała się ona czołową drużyną w zachodniej Polsce, toteż w 1963 została wcielona do wielosekcyjnego Międzyzakładowego Ludowego Klubu Sportowego Orzeł Międzyrzecz, stanowiąc jedną z jego sekcji sportowych (sekcję piłki siatkowej mężczyzn). Z powodów finansowych zlikwidowano ją w 1968, jednak już dwa lata później została ona reaktywowana (również w ramach MLKS Orzeł). Funkcjonowała ona do 1975, będąc w sezonie 1974/1975 o krok od awansu do II ligi. To właśnie w czasie jej działalności siatkówka stała się w Międzyrzeczu dyscypliną niezwykle popularną, ustępując jedynie piłce nożnej.
Sztandarowa sekcja
Na ponowną reaktywację męskiego zespołu siatkarskiego przyszło w "grodzie nad Obrą" czekać ponad dekadę. W międzyczasie tworzono jednak typowo amatorskie ekipy (najczęściej przy zakładach pracy), które grywały towarzysko w okolicznościowych spotkaniach, bądź turniejach, organizowanych na terenie województwa gorzowskiego. To właśnie ich członkowie z Tadeuszem Wolniewiczem na czele postanowili w 1986 założyć zespół, który następnie - po raz kolejny - przeszedł pod protektorat MLKS Orzeł, dając osiem lat później początek jednosekcyjnemu klubowi siatkarskiemu. Z czasem sekcja stała się dumą klubu, wygrywając w sezonie 1989/1990 swoją grupę klasy międzywojewódzkiej (III ligi), a rok później wywalczając awans do II ligi i stając się tym samym pierwszą w historii miasta drużyną, występującą w rozgrywkach ligowych szczebla centralnego.
Powstanie po rozłamie
Przemiany polityczno-społeczno-gospodarcze w Polsce po 1989 doprowadziły do stopniowego zmieniania struktury organizacyjnej rodzimych klubów sportowych. Już w 1990 - z inicjatywy Jerzego Rudnickiego - zawiązano w Międzyrzeczu Stowarzyszenie "Volleyball", które wzięło na siebie ciężar współfinansowania męskiej sekcji siatkarskiej MLKS Orzeł, chroniąc ją tym samym przed kolejną likwidacją. Do faktycznego wydzielenia tej sekcji z MLKS Orzeł (i jednoczesnej fuzji z Międzyszkolnym Klubem Siatkarskim Piast Międzyrzecz) doszło 19 grudnia 1994. Tego dnia odbyło się zgromadzenie założycielskie nowego klubu (jednosekcyjnego), podczas którego przyjęto jego statut, wybierając jednocześnie władze z Romanem Turowskim, jako Prezesem Zarządu. 19 stycznia 1995 podmiot ów został zarejestrowany w gorzowskim Urzędzie Wojewódzkim. W listopadzie 1997 MKS Orzeł rozpoczął - trwającą do dziś - współpracę z IWF w Gorzowie Wlkp. (oddziałem poznańskiej AWF). Zmianie uległa, więc nazwa klubu. Do kolejnej doszło trzy lata później (21 grudnia 2000) - po podpisaniu umowy z firmą gazowniczą Media Odra Warta Sp. z o.o. na współfinansowanie (obowiązywała ona do 31 grudnia 2007). W sezonie 2003/2004 drużyna prowadzona przez Nikołaja Mariaskina triumfowała w swojej grupie II ligi (2 miejsce w końcowej tabeli po fazie zasadniczej, a następnie zwycięska tura play-off po 3:0 w półfinale nad Morzem Bałtyk Szczecin oraz 3:0 w finale nad Politechniką Poznań) i uzyskała historyczny awans na zaplecze PLS. Pierwszy sezon w tej klasie rozgrywkowej przyniósł niespodziewany sukces w postaci 5 miejsca, choć zespołowi postawiono wyłącznie zadanie utrzymania się. Sztuka ta nie powiodła się rok później i po zajęciu przedostatniego miejsca nastąpił spadek szczebel niżej. Banicja w II lidze trwała zaledwie sezon, bowiem po nienajlepszej fazie zasadniczej (4 miejsce), nastąpiło przebudzenie w play-offach (3:0 nad AZS UZ Zielona Góra, 3:1 w półfinale nad Olimpią Sulęcin i 3:1 w finale nad GTS Gdańsk). Dało ono awans do barażów, w których międzyrzeczanie ograli 3:2 MKS MOS Będzin, uzyskując ponowną promocję do I ligi.
Tragedia pod Gościmiem
21 marca 2008 zapisał się w kalendarium, jako najczarniejszy dzień w historii klubu. Tego dnia około 13.40 doszło przed Gościmiem do wypadku drogowego z udziałem 4 siatkarzy Orła, w wyniku którego 2 z nich zginęło (Paweł Dziekanowski i Michał Pajor), a 2 zostało ciężko rannych (Kamil Sekuła i Patryk Wojtysiak).