Nadmienić trzeba, iż przez wiele lat w stanach Głębokiego Południa, do których należy Missisipi, właściwymi wyborami były prawybory, z uwagi na zupełną dominację Partii Demokratycznej, a raczej jej konserwatywno-segregacyjnego (m.in. Dixiecratów) skrzydła.
Stennis był potem wybierany ponownie w latach 1952, 1958, 1964, 1970, 1976 oraz 1982. Większą część swej kadencji zasiadał wraz z drugim senatorem z Missisipi, Jamesem Eastlandem (który zasiadał w Senacie w latach 1941 oraz 1943–1978). Eastland i Stennis są drugim pod względem długości wspólnego zasiadania senackim duetem z jednego stanu w historii, zaraz po Stromie Thurmondzie i Fritzu Hollingsie z Karoliny Południowej.
Stennis był autorem pierwszego w historii Senatu kodeksu etyki obowiązującego w tej izbie, a także pierwszym przewodniczącym stosownego komitetu.
Jako pierwszych z demokratycznych senatorów potępił publicznie działania Josepha McCarthy’ego, podczas gdy np. Eastland popierał go do samego końca.
„Ojciec nowoczesnej amerykańskiej marynarki wojennej” W latach 1969–1981 był przewodniczącym Senackiego Komitetu ds. Sił Zbrojnych, gdzie dał się poznać ze skutecznych na ogół działań na rzecz rozwoju marynarki wojennej. Z racji tego nadano mu potem zaszczytny przydomek „Ojca nowoczesnej amerykańskiej marynarki wojennej” (ang.