Η Fallin δεν διεκδίκησε επανεκλογή το 2006 ως υποδιοικητής. Διεκδίκησε την έδρα της 5ης περιφέρειας του Κογκρέσου που εκκενώθηκε από τον Ernest Istook. Στις 25 Ιουλίου, στις προκριματικές εκλογές του Ρεπουμπλικανικού Κόμματος, έλαβε τις περισσότερες ψήφους. Στις 22 Αυγούστου, αντιμετώπισε τον δεύτερο της κατάταξης, τον δήμαρχο της Οκλαχόμα Σίτι Μικ Κορνέτ, στις επαναληπτικές εκλογές του Δημοκρατικού Κόμματος. Κέρδισε με ποσοστό 63% των ψήφων.
Η Fallin εξελέγη στις 7 Νοεμβρίου, νικώντας τον Δημοκρατικό Paul David Hunter. Είναι η πρώτη γυναίκα που εκλέγεται στο Κογκρέσο από την Οκλαχόμα από το 1921. Η Alice Mary Robertson ήταν η πρώτη γυναίκα που εξελέγη στο Κογκρέσο των ΗΠΑ από την Οκλαχόμα. Παραιτήθηκε από το αξίωμά της στις 2 Ιανουαρίου 2007 προκειμένου να ορκιστεί στο Κογκρέσο στις 4 Ιανουαρίου 2007. Ο εκλεγμένος υποδιοικητής Jari Askins διορίστηκε από τον κυβερνήτη της Οκλαχόμα Brad Henry για να καλύψει τις υπόλοιπες ημέρες της θητείας της Fallin.
Η Fallin κέρδισε εύκολα την επανεκλογή της το 2008. Κατά την τελευταία θητεία της στο Κογκρέσο, η Fallin υπηρέτησε στην Επιτροπή Ενόπλων Υπηρεσιών της Βουλής των Αντιπροσώπων, στην Επιτροπή Μικρών Επιχειρήσεων της Βουλής των Αντιπροσώπων και στην Επιτροπή Μεταφορών και Υποδομών της Βουλής των Αντιπροσώπων.