Младен Кръстаич е роден в намиращия се в днешна Босна град Зеница в семейството на етнически сърби. Още от малък започва да тренира в местния Челик Зеница. Заради етническата война в Босна семейството му се премества да живее в сръбското градче Кикинда. Кръстаич продължава да тренира футбол в ОФК Кикинда, преди скаути на гранда Партизан (Белград) да го набележат. Впоследствие Младен Кръстаич преминава в Партизан (Белград) през 1995 г. По време на престоя си от 5 години записва 205 мача и вкарва 13 гола. През лятото на 2000 г. за сумата от 1.25 млн. евро преминава във Вердер Бремен, където за 4 сезона записва над 100 мача и вкарва 11 попадения. През 2004 г. подписва с Шалке 04 за четири години. За 5 сезона в „миньорите“ изиграва повече от 100 мача, а през 2009 е избран за капитан на отбора. През 2009 се връща в тима, открил го за големия футбол-Партизан[1]. След трансфера на Ненад Джорджевич в Криля Советов, Кръстаич става капитан на отбора. След края на 2010/11 слага край на кариерата си и става спортен директор на черно-белите.
За нацинолния отбор на има 59 изиграни мача и 2 вкарани гола. Част е от Великолепната четворка сръбски бранители, които допускат едва един гол по време на квалификациите за Мондиал 2006. Другите трима бранителя от Великолепната четворка са Неманя Видич (Манчестър Юнайтед), Ивица Драгутинович (Севиля) и Горан Гавранчич (Динамо Киев). През 2008 слага край на кариерата си в националния тим.