Kariera polityczna Izba Reprezentantów W roku 1994 zdobył nominację Partii Republikańskiej jako jej kandydat na kongresmena z 2. okręgu stanu Oklahoma (w którym mieści się Muskogee). Okręg ten uchodził dotychczas za bastion Partii Demokratycznej.
Początkowo spodziewano się, że jego przeciwnikiem będzie zasiadający z izbie od 1979 Mike Synar, ale ten, co było dla wielu dużym zaskoczeniem, został pokonany w prawyborach demokratycznych przez 71-letniego dyrektora szkoły Virgila Coopera. Coburn wygrał wybory stosunkiem 52 do 48% głosów, zostając tym samym pierwszym republikaninem z 2. okręgu, który zasiadał w Izbie od roku 1921.
Jako kongresmen generalnie uznawany był za konserwatystę. Zasiadając w izbie, opowiadał się m.in. za redukcją budżetu federalnego oraz ograniczeniem prawa do przerywania ciąży. Czasami jednak wyłamywał się z dyscypliny partyjnej i popadał w konflikty na tym tle z wpływowym spikerem Izby, Newtem Gingrichem.
W roku 1997 Coburn był sponsorem ustawy w sprawie przeciwdziałania AIDS, która nie została przyjęta. Przewidywała, iż wszyscy zakażeni wirusem HIV nie będą mogli z tego tytułu żadnych urzędów w publicznej służbie zdrowia.