Maja Ostaszewska urodziła się w 1972 r. w Krakowie. Po studiach w PWST w Krakowie związała się z warszawskim Teatrem Rozmaitości, potem z Teatrem Starym w Krakowie. Warszawskim debiutem aktorki była chłopczyca Rozalinda w przedstawieniu Piotra Cieślaka „Jak wam się podoba” Williama Shakespeare’a (1996).
Pierwszą dużą rolę filmową zagrała w „Przystani” (1997) Jana Hryniaka. Choć film nie trafił do normalnej dystrybucji, przyniósł Ostaszewskiej nagrodę na festiwalu w Gdyni. Udział w debiutanckim przedsięwzięciu Łukasza Barczyka „Patrzę na ciebie, Marysiu” (1999), emitowanym w II programie TVP, został bardzo pozytywnie przyjęty zarówno przez widzów, jak i krytyków. W 2000 r. podpisała angaż w Teatrze Narodowym.
Uważana za najwybitniejszą aktorkę swojego pokolenia.
Paszport POLITYKI otrzymała za wybitne role filmowe, za nowoczesne i wrażliwe aktorstwo, za grę, w którą zawsze się wierzy.