Volvieron a firmar con Warner Bros. Records en 1996 por US$80 000 000

Volvieron a firmar con Warner Bros. Records en 1996 por US$80 000 000 —una cifra que la banda afirmaba constantemente que se originaba en los medios de comunicación—, que se rumoreaba que era el contrato de grabación más grande de la historia en ese momento. ​ El álbum de 1996 del grupo, New Adventures in Hi-Fi , debutó en el número dos en los Estados Unidos y en el número uno en el Reino Unido. ​ Las cinco millones de copias vendidas del álbum fueron una inversión de la suerte comercial del grupo durante los cinco años anteriores. ​ La reacción de la crítica al álbum fue mayoritariamente favorable. En una retrospectiva de 2017 sobre la banda, Consequence of Sound la clasificó en tercer lugar entre los 15 álbumes de estudio de larga duración de R.E.M. ​ El álbum es el favorito de Stipe y lo considera la banda en su apogeo. ​ Mills dijo: «Por lo general, me lleva algunos años decidir dónde se encuentra un álbum en el panteón de trabajos grabados que hemos realizado. Este puede ser el tercero detrás de Murmur y Automatic for the People ». Según DiscoverMusic : «Podría decirse […] que New Adventures in Hi-Fi es menos inmediato y menos accesible, es un asunto de White Album extenso que llega a los 65 minutos. Sin embargo, si bien requirió algo de tiempo y compromiso por parte del oyente, el contenido del disco era rico, convincente y con frecuencia sorprendente. En consecuencia, el álbum ha seguido presionando para obtener reconocimiento y desde hace mucho tiempo se ha ganado su reputación como el álbum más olvidado de R.E.M.». ​ Si bien las ventas fueron impresionantes, estuvieron por debajo de sus récords anteriores de los principales sellos discográficos. El escritor de Time , Christopher John Farley, argumentó que las menores ventas del álbum se debieron a la disminución del poder comercial del rock alternativo en su conjunto. ​ Ese mismo año, se separaron del mánager Jefferson Holt, supuestamente debido a los cargos de acoso sexual que le imponía un miembro de la casa de la banda en Athens. ​ El abogado del grupo, Bertis Downs, asumió funciones de dirección. ​