Vereinskarriere

Majstorović spielte in der Jugend bei Övergrans IF und Habo FF. Erste Station im höherklassigen Männerfußball war ab 1995 IF Brommapojkarna. In der Winterpause der Spielzeit 1997/98 wechselte er zum SC Fortuna Köln in die 2. Bundesliga. Dort war er auf Anhieb Stammspieler und erzielte am 14. März 1998 beim 1:1-Unentschieden gegen den FC St. Pauli seinen einzigen Treffer im deutschen Profifußball. Mit einer Gelb-Roten Karte am letzten Spieltag verabschiedete er sich von der Fortuna und kehrte zurück nach Schweden.

Majstorović ging zu Västerås SK. Der Klub war in der Vorsaison aus der Allsvenskan abgestiegen und verpasste mit Majstorović als Tabellendritter nur knapp den direkten Wiederaufstieg. Im folgenden Jahr gelang nur ein Mittelfeldplatz, der immerhin die Qualifikation für die neue eingleisige zweite Liga bedeutete. Als in der Spielzeit 2000 erneut der Aufstieg verpasst wurde, verließ Majstorović nach zweieinhalb Jahren am Saisonende den Klub und wechselte in die Allsvenskan zu Malmö FF.

In der ersten Liga konnte sich Majstorović auf Anhieb in der Stammelf etablieren und im zweiten Jahr gelang mit dem Verein hinter Djurgårdens IF die Vizemeisterschaft. Mit dem Klub konnte er sich im vorderen Bereich der Tabelle festsetzen und mit 18 Saisonspielen trug er in der Spielzeit 2004 zum Meistertitel bei. Im selben Jahr wurde er von den Gegenspielern in der Liga zum unangenehmsten Gegner gewählt, wechselte aber noch in derselben Saison zum FC Twente Enschede.

Auch in der Eredivisie setzte sich Majstorović in der Startelf fest. Im Januar 2006 attackierte er jedoch im Training seinen Mannschaftskollegen Blaise Nkufo derart hart, dass es beinahe zu einer Schlägerei gekommen wäre. Nachdem Majstorović eine Woche später zu spät zum Training gekommen war, wurde er wegen dieser Disziplinlosigkeiten vom Verein freigestellt. Daraufhin wechselte er zum FC Basel, wo er in den 18 restlichen Saisonspielen fünf Tore erzielte. Mit dem Klub wurde er 2007 und 2008 Schweizer Pokalsieger und gewann 2008 den Schweizer Meistertitel. Kurz nach Ende der Spielzeit wurde bekannt, dass der kopfballstarke Abwehrspieler seinen bisherigen Arbeitgeber in Richtung AEK Athen verließ. Der ablösefreie Schwede unterschrieb beim griechischen Klub einen Dreijahresvertrag.

Am 16. August 2010 unterschrieb Majstorović beim schottischen Spitzenklub Celtic Glasgow einen Vertrag über zwei Spielzeiten. Auf Anhieb Stammkraft ersetzte er zeitweise den verletzten Scott Brown als Mannschaftskapitän. Während in der Meisterschaft hinter dem Lokalrivalen Glasgow Rangers der zweite Tabellenplatz belegt wurde, erreicht er mit der Mannschaft 2011 das Pokalfinale. An der Seite von Emilio Izaguirre, Glenn Loovens und Mark Wilson verhinderte er in der Abwehrreihe einen Torerfolg des FC Motherwell und trug somit zum 3:0-Erfolg und Titelgewinn bei. Die folgende Spielzeit war jedoch vom Verletzungspech überschattet. Zunächst verletzte er sich Mitte Dezember bei einem Zusammenprall mit David Robertson vom FC St. Johnstone, so dass er mit einem Jochbeinbruch mehrere Wochen ausfiel. Nach seiner Rückkehr in die Mannschaft Anfang Februar verletzte er sich wenige Wochen später bei einem Aufenthalt bei der Nationalmannschaft. Im Training verletzte er sich in einem Zweikampf mit Zlatan Ibrahimović, ein Kreuzbandriss beendete die Spielzeit für ihn vorläufig und beendete zudem Hoffnungen auf eine Teilnahme an der EM-Endrunde 2012.

Der zwischenzeitlich vertragslose Majstorović kehrte im Sommer 2012 in sein Heimatland zurück. Im Mai unterschrieb er einen ab August – in diesem Monat öffnet das Sommertransferfenster in Schweden – gültigen Vertrag bei AIK mit Laufzeit bis Ende 2014. Im Sommer 2013 überwarf er sich jedoch mit Trainer Andreas Alm und der Klubführung, sein Vertrag wurde schließlich Anfang Juni mit Wirkung zum 6. Januar 2014 aufgelöst. Im Februar 2014 kündigte er das Ende seiner aktiven Karriere an, um die Ausbildung zum Spieleragenten zu beginnen und sich dem Geschäft seines vormaligen Beraters Rodger Linse anzuschließen.

Nationalmannschaft

Majstorović debütierte am 16. Februar 2003 beim 3:2-Erfolg über die Landesauswahl von Katar im Rahmen des King’s Cup in der schwedischen Nationalmannschaft. Vier Tage später erzielte er in seinem dritten Länderspiel beim 4:1-Sieg über Nordkorea mit dem Treffer zum zwischenzeitlichen 4:0 sein erstes Länderspieltor. In den folgenden Jahren kam er nur unregelmäßig zum Einsatz und zählte vor der Weltmeisterschaft 2006 zum erweiterten Nationalkader Schwedens, wurde jedoch letztendlich nicht berücksichtigt. Da er 2008 in den Länderspielen gegen die Türkei und Brasilien in der Startelf stand, galt er als aussichtsreicher Kandidat im Kampf mit Olof Mellberg, Fredrik Risp und Petter Hansson um einen Mittelfeldplatz in der schwedischen Landesauswahl bei der Europameisterschaft 2008. Als Nationaltrainer Lars Lagerbäck am 13. Mai 2008 das Aufgebot bekannt gab, gehörte Majstorović zum 23 Spieler starken Kader. Die Mannschaft scheiterte beim Turnier in der Vorrunde.

Nachdem sich die schwedische Auswahlmannschaft nicht für die WM-Endrunde 2010 hatte qualifizieren können, gehörte Majstorović nach der erfolgreichen Qualifikation zur Europameisterschaft 2012 zu den Kandidaten für eine erneute Endrundenteilnahme. Verletzungsbedingt (s. o.) verpasste er jedoch das Turnier. Bis zum Sommer 2013 gehörte er noch der Nationalelf an, nach seiner Demission bei AIK war er ohne Spielpraxis und Nationaltrainer Erik Hamrén verzichtete nach 50 Länderspieleinsätzen auf seine Dienste.