Deux ans après, ils sont retournés vivre en Australie, et Kristina Keneally a alors été naturalisée australienne. Leur second fils, Brendan, est venu au monde au cours de cette même année 2000.
En 2003, elle est élue députée à l'Assemblée législative de Nouvelle-Galles du Sud pour la circonscription d'Heffron, après une difficile primaire interne à l'ALP contre la sortante, Deirdre Grusovin. Son investiture est également due aux règles internes au parti en termes de discrimination positive et qui imposait qu'une femme soit désignée, alors même que Ben Keneally, son époux, était lui aussi intéressé par une carrière politique. Dans son premier discours en tant que parlementaire, elle a fait connaître son engagement pour la justice sociale, l'égalité des chances et sa foi catholique.
Carrière ministérielle
Elle est ensuite nommée ministre des Services aux handicapés en 2007, et promet alors de rénover les établissements spécialisés obsolètes, reprenant en cela la promesse non tenue de l'un de ses prédécesseurs. Elle change de portefeuille en pour devenir ministre de l'Aménagement du territoire. À ce poste, elle a géré de façon stricte la construction d'une conduite de désalinisation entre les villes Erskineville et Turnell, en organisant le détournement de la circulation automobile et s'assurant du respect des normes environnementales.
Elle est présentée en comme une adversaire possible du Premier ministreNathan Rees pour la présidence de la fédération de l'ALP et donc la direction du gouvernement. Elle répond à ces allégations en affirmant que « [Rees] a tout mon soutien », et des rumeurs ajoutent qu'elle aurait insisté sur le fait qu'elle ne serait jamais Premier ministre. Face au retour de ces rumeurs en novembre, elle déclare « J'ai toujours soutenu le Premier ministre, que ce soit Bob Carr, Morris Iemma et maintenant Nathan Rees. Maintenant, il est temps de laisser ces ridicules supputations derrière nous ».
Premier ministre (2009-2011)
Malgré toutes ces déclarations, elle se présente le à la présidence de l'ALP de Nouvelle-Galles du Sud contre Rees, qu'elle défait par 45 voix contre 21, grâce au soutien de l'aile droite du groupe parlementaire. Rees annonce alors qu'il démissionnera avant la fin de la journée et que, pour lui, il ne fait aucun doute que son adversaire ne peut être que le « pantin » du sénateur Eddie Obeid et du député Joe Tripodi, chefs de file de la droite des travaillistes. Face à ces accusations, elle a répondu « Je ne suis le pantin de personne, la protégée de personne, la fille de personne ».
Aux élections du , la coalition Libéral/National obtient 51,1 % des voix et 69 députés sur 93, tandis que les travaillistes, dont elle était chef de file, s'effondrent avec 25,6 % des suffrages et 20 sièges, soit 32 de moins que lors du précédent scrutin. Consécutivement à cette défaite, la plus large en Australie depuis la Seconde Guerre mondiale, elle renonce à diriger la fédération travailliste de l'État, tout en conservant son siège à l'Assemblée législative. Elle est remplacée comme premier ministre le 28 mars par le libéral Barry O'Farrell.
