Bei den Kongresswahlen des Jahres 2010 wurde Palazzo im vierten Kongresswahlbezirk von Mississippi in das Repräsentantenhaus der Vereinigten Staaten in Washington, D.C. gewählt, wo er am 3. Januar 2011 die Nachfolge des ihm zuvor unterlegenen DemokratenGene Taylor antrat. Bei den Wahlen 2012 setzte Palazzo sich mit 64 zu 29 Prozent der Stimmen gegen den Demokraten Matthew Moore durch. Im Jahr 2014 konnte er mit 69,9 % der Stimmen erneut gegen den Demokraten Matt Moore gewinnen. 2016 siegte er mit 65 % unter anderem gegen den Demokraten Mark Gladney. Die Wahlen des Jahres 2018 konnte er mit 68,2 Prozent gewinnen. Er besiegte unter anderem Jeramey Anderson von der Demokratischen Partei sowie Lajena Sheets von der Reform Party. Im Jahr 2020 konnte er ohne Gegenkandidaten zur Wahl antreten und wurde dementsprechend mit 100 % wiedergewählt. Zuvor hatte er sich in der Vorwahl seiner Partei mit 66,8 % gegen drei Mitbewerber durchgesetzt.[5]
Die Primary (Vorwahl) seiner Partei für die Wahlen 2022 am 10. März verlor er mit 46 zu 54 % gegen Mike Ezell, nachdem er den ersten Teil der Vorwahl noch mit 6 % Vorsprung auf Ezell gewinnen konnte. Die Niederlage steht in Zusammenhang mit Vorwürfen der Korruptions und Vetternwirtschaft gegen Palazzo, unter anderem soll er Wahlkampfmittel zweckentfremdet haben.[6] Er schied damit am 3. Januar 2023 aus dem Repräsentantenhaus aus.[3]
