W 1997 r. została wybrana do Izby Gmin z okręgu Bolton West. Przez większość kampanii była w ciąży z pierwszym z czwórki swoich dzieci, które urodziło się 11 dni po wyborach. Jako parlamentarzystka trafiła do komisji finansów, była także asystentem parlamentarnym ministra rolnictwa. Po reelekcji w 2001 r. została ekonomicznym sekretarzem skarbu. Jednym z jej zadań było wówczas znalezienie pieniędzy na wzmożone działania antyterrorystyczne. We wrześniu 2004 r. stanęła na czele Urzędu Gabinetu, a trzy miesiące później została ministrem edukacji i zdolności. Równocześnie została członkiem Tajnej Rady. Na stanowisku ministra Kelly doprowadziła do wydłużenia godzin otwarcia szkół, które od tamtej pory są czynne między 8 a 18. Wprowadziła również opiekę dla dzieci pracujących rodziców.
W 2006 r. Kelly stanęła na czele nowo utworzonego resortu ds. społeczności i samorządów lokalnych. Równocześnie pełniła funkcję ministra ds. kobiet i równouprawnienia (co było o tyle kontrowersyjne, że jej poglądy są bardzo dalekie od feministycznych). 28 czerwca 2007 nowy premier Gordon Brown powołał ją na urząd ministra transportu. 24 września 2008 r. Kelly ogłosiła, że zamierza zrezygnować ze stanowiska przy okazji następnej przebudowy gabinetu.