Coburn przyrzekł w czasie swej pierwszej kampanii wyborczej, iż opuści Izbę po trzech dwuletnich kadencjach. W czasie republikańskich prawyborów prezydenckich w 2000 poparł byłego dyplomatę i konserwatywnego działacza Alana Keyesa, ale potem stał się jednym z najbardziej żarliwych popleczników prezydenta George’a W. Busha. Jego miejsce w Izbie zajął demokrata Brad Carson.

Senat Stanów Zjednoczonych W roku 2004 został wysunięty przez republikanów jako kandydat do Senatu Stanów Zjednoczonych w miejsce ustępującego partyjnego kolegi, Dona Nicklesa. Wygrał wybory większością 53 do 41%, pokonując swego następca w Izbie, demokratę Carsona. Kandydatka Partii Zielonych w tych wyborach, Sheila Bilyeu, zdobyła 5,99%. Jego pierwsza kadencja upłynęła 3 stycznia 2011 roku.

Był członkiem Komitetów Prawnego, Bezpieczeństwa Narodowego i Spraw Rządowych oraz ds. Indian. Notabene wśród rodowitych mieszkańców nie cieszy się żadną popularnością i bywa oskarżany nawet o rasizm na tym tle.

Jego mianowanie do Komitetu Prawnego było o tyle niezwykłe, iż nie miało to prawie nigdy miejsca w przypadku senatora zaledwie pierwszej kadencji i bez wykształcenia prawniczego.

Z uwagi na jego częsty sprzeciw wobec wielu ustaw nadano mu przydomek Dr. No.