Aunque existen indicios de la existencia de pobladores en este municipio desde el Paleolítico (en la zona de Silvarrei se localizó un bifaz de tipo achelense), las primeras huellas importantes del pasado histórico de Outeiro de Rei se remontan al período megalítico (4000-2000 a.C.). La gran abundancia de mámoas localizadas en su término, entre las que destacan la Medorra da Pedra Dereita en Martul, así como los ajuares encontrados en dichos monumentos funerarios (conservados en la actualidad en museos y colecciones privadas) y los grabados rupestres o petroglifos esparcidos por sus montes, ponen de manifiesto la presencia durante esta etapa de una población bastante numerosa y activa.

Desde entonces y hasta la actualidad con las referencias bibliográficas y arqueológicas existentes, resulta lógico pensar que este lugar estuvo continuamente habitado. Primero, por la población castreña (800 a.C.-100 d.C.), siendo varios los castros catalogados en este ayuntamiento, todos ellos sin excavar y entre los que se encuentra el castro de Candai, ubicado en los límites de las parroquias de Aspai y Candai.

La llegada de los suevos a Galicia (410 d.C. aprox.) supuso la organización político-administrativa del territorio lucense en condados, integrándose la práctica totalidad del actual ayuntamiento en el denominado condado de Superata (Sobrada). Para este período merece especial mención la aldea de Astariz (Caboi), la cual, según tradición popular era llamada Coto Real y contaba con sus propias autoridades.

Después de la invasión árabe y posterior reconquista de los reinos cristianos del norte de la Península (Baja Edad Media, a partir del s. VIII) el obispo lucense Odario fue el encargado de repoblar los territorios de la provincia de Lugo, entre los que se encontraban lugares del actual municipio de Outeiro de Rei, como las parroquias de Silvarrei, Parada y Cela, que aparecen nombradas en el testamento de este obispo.

Posteriormente, durante los siglos XII e XIII el territorio gallego se divide en numerosos cotos bajo jurisdicción señorial, entre los que se citan Astariz, Cela, Taboi o Aguiar. Inicialmente, la tierra de Outeiro de Rei la poseyó el señorío de Sarria, pero por donación real de Pedro I pasó al señor de Lemos a mediados del s. XIV (1360). A finales del siglo XV (1480) el conde de Lemos cede en feudo las tierras de Castro de Rei y Outeiro de Rei al Mariscal Pardo de Cela, con la única finalidad de que Pardo de Cela le entregase por esposa a su hija doña Constanza, sin que los hijos del Mariscal pudieran usar el feudo, de tal forma que este volviese a manos del conde.

En 1501, en virtud del convenio subscrito entre el II conde de Lemos y la reina Isabel la Católica, Isabel concedió a Rodrigo las villas de Sarria, Castro de Rei y Outeiro de Rei que el conde de Lemos ya consideraba suyas. Durante toda la Baja Edad media (s. XI-XV) el territorio de Outeiro de Rei se vio sometido al poder de los señores feudales (condado de Lemos) y eclesiástico (obispados de Lugo y Mondoñedo), que no se vieron libres de las revueltas populares derivadas de sus abusos de poder.
En la segunda mitad del s. XV, al igual que sucedió en toda Galicia, estas tierras sufren con crudeza las revueltas irmandiñas del campesinado contra los poderes de los señores feudales. En este momento se destruyen casi todos los castillos y fortalezas de Galicia entre ellos la fortaleza de Sobrada de Aguiar, derrumbada en 1467 por los irmandiños y reconstruida a finales del s. XV por Fernán Pérez de Ribadeneira.

La tierra de Outeiro de Rei fue cuna de algunos de los principales linajes nobiliarios de Galicia, entre los que destacan los Gayoso, los Montenegro o los Aguiar. Estos construyeron aquí primero sus castillos-fortalezas y una vez finalizada la inestabilidad medieval (s. XVI), llevaron a cabo la transformación civil de dicha arquitectura militar, surgiendo los pazos y casas señoriales.

Su posición limítrofe con la capital de la provincia hizo de Outeiro de Rei un lugar de residencia apetecido para los nobles y también para la pequeña hidalguía. Buena prueba de ello es la importante concentración de casas señoriales en este término entre las que ocupan un lugar destacado: el pazo de Mirapeixe (Santa Mariña), solar de origen de los Gayoso; la Casa Fuerte de Outeiro de Rei, con origen en una fortaleza medieval del siglo XV y que fue ocupada por la familia irlandesa O’Kelly y posteriormente pasó a manos de los Gayoso; la casa-torre de A Barreira (Santiago de Gayoso) originaria de 1575 o el pazo de Guevara, levantado a finales del siglo XVII por el linaje Pardo-Rivadeneira.

Pero Outeiro de Rei no sólo conserva una arquitectura civil de interés, también debemos destacar su arquitectura religiosa; sus veintisiete iglesias y diez capillas fueron construidas mayoritariamente durante el período barroco (s. XVII-XVIII), con alguna excepción como son los templos de Francos, Martul y Robra. Aunque presentan remodelaciones posteriores, todavía conservan partes de su primitiva fábrica románica, destacando los ábsides (cabeceras) y la sobria ornamentación (en puertas, ventanas, canecillos y capiteles).

En el siglo XVIII se experimenta un notable desarrollo de las comunicaciones en Galicia con la construcción de los Caminos Reales (época de Carlos III), que en la mayoría de los casos vinieron a mejorar caminos e infraestructuras que ya existían desde época romana. Este es el caso del Camino Real de Lugo a Betanzos que pasaba por Outeiro de Rei, y del destacado paso por la Ponte Vella de Rábade (entre Rábade e Outeiro), antesala de la ciudad de Lugo. Este puente está intimamente ligado al Pazo de Mirapeixe (origen del linaje de los Gayoso), y para poder atravesarlo había que pagar impuesto de pontazgo.

Durante el s. XIX la historia de Galicia está ligada a la Guerra de Independencia Española (1808-1814), produciéndose escaramuzas y fuerte resistencia en la comarca de Lugo contra las tropas francesas en la ofensiva gallega de 1809. Las guerrillas populares consiguen hacer de Galicia el primer territorio español liberado del ejército francés. Las guerras carlistas del XIX también se dejaron sentir en Outeiro de Rei, siendo la Ponte Vella de Rábade escenario de varios fusilamientos.