Aínda que existen indicios da existencia de poboadores neste municipio dende o Paleolítico (na zona de Silvarrei localizouse un bifaz de tipo achelense), as primeiras pegadas importantes do pasado histórico de Outeiro de Rei remóntanse ao período megalítico (4000-2000 a.C.). A grande abundancia de mámoas localizadas no seu termo, entre as que destacan a Medorra da Pedra Dereita en Martul, así como os enxovais encontrados en ditos monumentos funerarios (conservados na actualidade en museos e coleccións privadas) e os gravados rupestres ou petroglifos esparexidos polos seus montes, poñen de manifesto a presenza durante esta etapa dunha poboación bastante numerosa e activa.

Dende entón e ata a actualidade coas referencias bibliográficas e arqueolóxicas existentes, resulta lóxico pensar que este lugar estivo continuamente habitado. Primeiro, pola poboación castrexa (800 a.C.-100 d.C.), sendo varios os castros catalogados neste concello, todos eles sen escavar e entre os que se encontra o castro de Candai, situado nos límites das parroquias de Aspai e Candai.

A chegada dos suevos a Galicia (410 d.C. aprox.) supuxo a organización político-administrativa do territorio lucense en condados, integrándose a práctica totalidade do actual concello no denominado condado de Superata (Sobrada). Para este período merece especial mención a aldea de Astariz (Caboi), a cal, segundo tradición popular era chamada Coto Real e contaba coas súas propias autoridades.

Despois da invasión árabe e posterior reconquista dos reinos cristiáns do norte da Península (Baixa Idade Media, a partir do s. VIII) o bispo lucense Odoario foi o encargado de repoboar os territorios da provincia de Lugo, entre os que se encontraban lugares do actual municipio de Outeiro de Rei, como as parroquias de Silvarrei, Parada e Cela, que aparecen nomeadas no testamento deste bispo.

Posteriormente, durante os séculos XII e XIII o territorio galego divídese en numerosos coutos baixo xurisdición señorial, entre os que se citan Astariz, Cela, Taboi ou Aguiar. Inicialmente a terra de Outeiro de Rei posuíuna o señorío de Sarria, mais por doazón real de Pedro I pasou ao señor de Lemos a mediados do s. XIV (1360). A finais do século XV (1480) o conde de Lemos cede en feudo as terras de Castro de Rei e Outeiro de Rei ao Mariscal Pardo de Cela, coa única finalidade de que Pardo de Cela lle entregase por esposa á súa filla dona Constanza, sen que os fillos do Mariscal puidesen usar o feudo, de tal modo que este volvese a mans do conde.

En 1501, en virtude do convenio subscrito entre o II conde de Lemos e a raíña Isabel a Católica, Isabel concedeu a Rodrigo as vilas de Sarria, Castro de Rei e Outeiro de Rei, que o conde de Lemos xa consideraba súas. Durante toda a Baixa Idade Media (s. XI – XV) o territorio de Outeiro de Rei viuse sometido ao poder dos señores feudais (condado de Lemos e eclesiástico (bispados de Lugo e Mondoñedo), que non se viron libres das revoltas populares derivadas dos seus abusos de poder.
Na segunda metade do s. XV, ao igual que sucedeu en toda Galicia, estas terras sofren con crueza as revoltas irmandiñas do campesiñado contra os poderes dos señores feudais. Neste momento destrúense case todos os castelos e fortalezas de Galicia, entre eles a fortaleza de Sobrada de Aguiar, derrubada en 1467 polos irmandiños e reconstruída a finais do s. XV por Fernán Pérez de Ribadeneira.

A terra de Outeiro de Rei foi o berce dalgúns dos principais liñaxes nobiliarios de Galicia, entre os que destacan os Gayoso, os Montenegro ou os Aguiar. Estes construíron aquí primeiro os seus castelos-fortalezas e unha vez finalizada a inestabilidade medieval (s. XVI), levaron a cabo a transformación civil de dita arquitectura militar, xurdindo os pazos e casas señoriais.

A súa posición limítrofe coa capital da provincia fixo de Outeiro de Rei un lugar de residencia apetecido para os nobres e tamén para a pequena fidalguía. Boa proba de elo é a importante concentración de casas señoriais neste termo entre as que ocupan un lugar destacado: o pazo de Mirapeixe (Santa Mariña), solar de orixe dos Gayoso; a Casa Forte de Outeiro de Rei, con orixe nunha fortaleza medieval no século XV e que foi ocupada pola familia irlandesa O´Kelly e posteriormente pasou a mans dos Gayoso; a casa -torre de A Barreira (Santiago de Gayoso) orixinaria de 1575 ou o pazo de Guevara, levantado a finais do século XVII polos Pardo-Rivadeneira.

Pero Outeiro de Rei non só conserva unha arquitectura civil de interese, tamén debemos destacar a súa arquitectura relixiosa; as súas vintesete igrexas e dez capelas foron construídas maiormente durante o período barroco ( s. XVII-XVIII), con algunhas excepcións como son os templos de Francos, Martul e Robra. Aínda que presentan remodelacións, aínda conservan partes da súa primitiva fábrica románica destacando as ábsidas (cabeceiras) e a sobria ornamentación (en portas, ventás, canzorros e capiteis).

No século XVIII experiméntase un notable desenvolvemento nas comunicacións en Galicia coa construción dos Camiños Reais (época de Carlos III), que na maioría dos casos viñeron a mellorar camiños e infraestruturas que xa existían dende época romana. Este é o caso do Camiño Real de Lugo a Betanzos que pasaba por Outeiro de Rei, e do destacado paso da Ponte Vella de Rábade (entre Rábade e Outeiro), antesala da cidade de Lugo. A Ponte Vella está intimamente ligada ao Pazo de Mirapeixe (orixe da liñaxe dos Gaioso), e para poder atravesala había que pagar imposto de pontazgo.

Durante o século XIX a historia de Galicia está ligada á Guerra de Independencia Española (1808 – 1814), producíndose escaramuzas e forte resistencia na comarca de Lugo contra as tropas francesas na ofensiva galega de 1809. As guerrillas populares conseguen facer de Galicia primeiro territorio español liberado do exército francés. As guerras carlistas do XIX tamén se deixaron sentir en Outeiro de Rei, sendo a Ponte Vella de Rábade escenario de varios fusilamentos.