Do kadry „Radziu” trafił jeszcze w czasach gry w Pogoni. Jako pierwszy powołał go trener Henryk Apostel, a miało to miejsce w 1994 roku. Wówczas jednak nie dane mu było jeszcze zadebiutować w meczu z Białorusią (1:1). Szansę pokazania umiejętności otrzymał dopiero 5,5 roku później – od Jerzego Engela – w spotkaniu towarzyskim z Hiszpanią (0:3) 26 stycznia 2000 roku na Estadio Municipal Cartagonova w Kartagenie. Dla obu panów był to debiut w drużynie narodowej – dla jednego na ławce trenerskiej, dla drugiego na boisku. Majdan spędził na placu gry 90 minut. W polskim zespole pojawili się m.in. Marek Zając, Radosław Michalski, Sławomir Majak i Radosław Gilewicz.

Reprezentacyjna kariera Majdana trwała krótko. W ciągu 2,5 roku rozegrał zaledwie 7 spotkań w bluzie z orzełkiem. Rywalizacja na pozycji bramkarza była duża i musiał zadowolić się rolą drugiego lub nawet trzeciego golkipera. Najważniejszy mecz w kadrze zdołał jednak zaliczyć – ze Stanami Zjednoczonymi (3:1) na mistrzostwach świata w Korei Płd. i Japonii w 2002 roku. To był jego przedostatni występ. Z reprezentacją pożegnał się po mundialu. W Szczecinie na stadionie Pogoni biało-czerwoni zmierzyli się towarzysko z Belgią (1:1) w debiucie selekcjonerskim Zbigniewa Bońka. „Radziu” przebywał na murawie przez pierwsze 45 minut. Na boisku pojawili się wówczas także Arkadiusz Głowacki, Mariusz Lewandowski, Bartosz Karwan i Maciej Żurawski.

Majdan zakończył karierę w 2010 roku, ale przez pewien czas jeszcze grał w piłkę – w reprezentacji Polski w beach soccerze. Później imał się różnych prac. W Polonii Warszawa, w której kończył karierę, pełnił funkcję dyrektora sportowego, kierownika drużyny, a także trenera bramkarzy. Próbował też sił w biznesie, polityce i działalności społecznej.

Dzięki małżeństwu z wokalistką Dorotą „Dodą” Rabczewską (2005-2008) stał się wręcz celebrytą. Pojawiał się m.in. w teledyskach zespołu Virgin, reklamach, programach typu reality show, „Tańcu z gwiazdami”, a później także w serialach telewizyjnych (już jako partner prezenterki telewizyjnej Małgorzaty Rozenek, z którą potem się ożenił). Był nawet gitarzystą w zespole rockowym The Trash. W mediach występował również jako ekspert przy okazji meczów ekstraklasy – w Eurosporcie, TVP Sport i Canal+ Sport.

► Uczestnik mistrzostw świata w Korei Płd. i Japonii (2002)
► Mistrz Polski z Wisłą Kraków (2004, 2005)
► Wicemistrz Polski z Pogonią Szczecin (2001)
► Puchar Grecji z PAOK-iem Saloniki (2003)