Byrne connaît son premier succès au cinéma dans le très acclamé Two hands de Gregor Jordan (Ned Kelly, Buffalo Soldiers), aux côtés de Heath Ledger. Le film, qui fait partie des classiques du cinéma australien, a été l’un des plus grands succès au box-office australien lors de sa sortie. L’année suivante, elle tourne aux côtés de Sam Neill et Sinéad Cusack dans My Mother Frank. Malgré les critiques unanimes, le film est un échec auprès du public.
La même année, elle rencontre la réalisatrice hong-kongaise Clara Law qui lui offre son tout premier rôle en tant qu’actrice principale dans le surréaliste La déesse de 1967. Byrne y interprète une jeune fille aveugle cachant des secrets troublants. Son interprétation, alliant force et fragilité, lui a valu la Volpi Cup de la meilleure actrice au festival de Venise en 2001.
En 2002, elle est remarquée par George Lucas qui lui offre, tout comme il l’avait fait pour Keira Knightley et Sofia Coppola, le rôle de la suivante de la reine Amidala dans Star Wars : épisode II - L'Attaque des clones aux côtés de Natalie Portman.
Malheureusement pour Byrne, beaucoup de scènes sont coupées lors du montage final. Néanmoins, la jeune femme vient de tourner sa toute première superproduction américaine. Elle sera ensuite approchée pour tourner dans le premier long métrage de Matt Dillon, City of Ghosts, où elle partage l’affiche avec Gérard Depardieu et Natascha McElhone.
En 2003, Rose Byrne tente sa chance en Grande-Bretagne où elle tourne Rose et Cassandra (I Capture the Castle) tiré du roman I Capture the Castle de Dodie Smith. Elle y interprète une sœur excentrique au côté de la débutante Romola Garai. Les performances des deux jeunes femmes sont plébiscitées par la presse anglaise. Puis les tournages s’enchaînent ; tout d’abord, The Night We Call It a Day au côté de Dennis Hopper. Le film est projeté à plusieurs festivals, mais se fait néanmoins discret auprès du public. Puis The Rage in Placid Lake, une comédie australienne qui lui vaut une nomination aux AFI awards.
En 2004, elle poursuit sa carrière hollywoodienne et tourne Wicker Park, remake américain de L'Appartement de Gilles Mimouni, où elle interprète le rôle détenu à l’origine par Romane Bohringer. Elle y partage l’affiche avec Josh Hartnett et Diane Kruger.
Malgré les critiques partagées, l’interprétation de Rose Byrne est plébiscitée.
C’est en tournant dans Troie de Wolgang Petersenque Byrne connaît son tout premier succès international. Elle campe le rôle de Briséis, une jeune prêtresse d’Apollon prise sous l’aile d’Achille, interprété par l'acteur américain Brad Pitt, lors de la prise de Troie par les Grecs. Malgré un petit rôle, Rose Byrne s’impose comme la révélation du film. Son interprétation lui vaut des éloges de plusieurs quotidiens américains qui la classent parmi les jeunes actrices à suivre à Hollywood.
Elle est ensuite sollicitée par la BBC pour tourner dans Casanova de nouveau avec Peter O'Toole, ainsi que dans un film indépendant mettant également en vedette Snoop Dog et Dylan McDermott.
En 2006, elle tourne sous la caméra de Sofia Coppola dans le très controversé Marie-Antoinette où elle interprète l’emblématique Yolande de Polastron, meilleure amie de Marie-Antoinette, campée par Kirsten Dunst.
En 2007, elle apparaît dans deux films du même réalisateur, Sunshine, le thriller de science-fiction de Danny Boyle, où elle interprète une pilote en mission vers le Soleil, et 28 Semaines Plus Tard, la suite de 28 Jours plus tard, également coproduit par Boyle.
En 2008, elle est à l'affiche du drame The Dead Girl de Karen Moncrieff aux côtés de James Franco, Toni Collette, Kerry Washington et Brittany Murphy, ainsi que d'une comédie dramatique Just Buried dans un registre plutôt morbide. Enfin, retour aux sources avec The Tender Hook, un film noir se déroulant à Sydney dans les années 1920, au côté de Hugo Weaving.
En 2011, elle tient l'un des rôles principaux féminins de la comédie Mes meilleures amies et joue le rôle de Moira MacTaggert dans le film X-Men : Le Commencement de Matthew Vaughn.