Non se ten coñecemento de industrias líticas do Paleolítico na parroquia, pese á existencia de terrazas fluviais subministradoras de material; do que hai constancia é de varias mámoas, algunhas arrasadas, ao longo da divisoria de augas Deza Superior-Asneiro. A necrópole do Couto estaba formada por uns seis túmulos, dos que tres foron desfeitos en 1981 por un veciño, que roturou monte para transformalo en pradería. Consérvase o de Sete Camiños, bastante afectado pola pista asfaltada de Vistalegre a Barcia. A esta necrópole pertencía a gran mámoa do Coto de Vistalegre, tradicionalmente empregada para o abenzoamento dos campos de cultivo pola festa de San Antonio (13 de xuño). No contorno do Couto foi descuberto, en 1999, un morteiro ou muiño de man, que consistía nunha escavación elíptica feita nun bloque de "dente de cabalo" (rocha desta zona), e tres anacos moi reducidos de cerámica prehistórica. Estes achados fan supoñer que aquí estivo instalado un asentamento neolítico contemporáneo dos túmulos.
Outro posible enclave atópase por abaixo de O Tarreo, na finca de O Viveiro, na que foron descubertas tres ou catro pedras pulidas, que puideron corresponder a muiños planos de man, durante a roturación feita a mediados do século pasado. Esta referencia conta con apoio folclórico relacionado co gran penedo situado a carón, que recibe o nome de A Pena dos Mouros. A lenda afirma que alí vivían escondidos os mouros, que entraban por unha porta que había abaixo de tres escalóns e pola que se accedía a unha cova, desde a cal existía un pasadizo subterráneo ata o castro de Lodeiro, a 2.400 metros.
No límite con Ramil, aldea de Gresande, apareceron restos doutro posible poboado neolítico: Machados pulidos que conserva un veciño. Outros túmulos atópanse no límite con Barcia, caso de Coto Espiñeira, ou xa na parroquia de Vilatuxe, nun lugar situado entre Castro de Arriba e Castro de Abaixo, que pertenceu, antigamente, a Soutolongo.
Os poboados abertos do Neolítico son sustituidos por outros cerrados e permanentes, con estruturas de protección ben consolidadas e adaptadas ao medio físico: Os castros. En Soutolongo hai dous moi diferentes: O de Lodeiro, a 644 metros de altura, na divisoria Deza-Asneiro, e o de Vilar, nun meandro do Asneiro a 469 metros.
O de Lodeiro é un dos que se atopa a maior altura, respecto dos trinta e dous xacementos similares existentes no concello. Domina unha panorámica visual moi ampla e permitíu aos seus primitivos habitantes controlar con facilidade todo o seu contorno. No castro diferencianse dous espazos, o superior ou aurela e o anexo ou antecastro, que ocupan unha superficie de, aproximadamente, 2,65 Ha. Tanto nun recinto como no outro teñen aparecido restos arqueolóxicos relacionados con utensilios da vida diaria dos seus antigos moradores. No pasado motivou unha interminable disputa acerca da súa titularidade entre Soutolongo, Vilatuxe e Lodeiro. Por esa causa teñen aparecido lendas relacionadas coa existencia dunha pequena ermida na Aurela do Castro e na que se atopaba a vella cruz de prata conservada na igrexa de Soutolongo. Segundo a lenda, cando chegou o momento de abandonar a ermida, Soutolongo e Vilatuxe entablaron unha dura disputa para determinar quen debía levar a valiosa cruz. En vista de que non foi posible chegar a un acordo, propuxeron que debía decidir o azar, poñendo a cruz nun carro tirado por unha parella de bois. Os bois marcharon antepostos (sen que ninguén os guiara) cara a Soutolongo. En consecuencia, a cruz terminou na igrexa desta parroquia.
O castro de Vilar ou "Daquel Lado", para os veciños de Botos, instalouse nun gran meandro do Asneiro, río que o delimita por varios lados formando unha liña envolvente duns 950 metros. Consta de dous recintos, unha croa ovalada e outro delimitado por un foxo tranversal trazado no estreitamento do meandro, o istmo, duns 175 metros de ancho. A superficie ocupada é de 4,75 Ha., pero, co meandro, chega a 7,5. Centrou disputas territoriais entre veciños de Vilar e Sestelo (Botos), xa que estes últimos tiñan establecida unha liña fronteiriza cun valado, transpasando o foxo. Os conflitos chegaron á actualidade, como se puxo de manifesto en 2012 co ensanche da pista que unía Vilar con Sestelo, tentando pasala polo castro, ao ser este o trazado seguido por un camiño aberto en 1920 para acceder ao muiño da Fábrica, que pertencía a Vilar.
Coa desaparición da cultura castrexa e a ocupación romana entramos nun vacío histórico, no "milenio medieval", desde o século V ata o XVI. En torno ao castro de Lodeiro formáronse catro aldeas: Castro de Arriba, Castro de Abaixo, Lodeiro e Xar, que se expandiron polos vales do rego de Sampaio, Portaouteiro e Regueira. No castro de Vilar formouse unha aldea no val do rego de Chousa do Muiño, moi cerca de Campo Dozón, da que quedan restos arqueolóxicos (tellas, unha canalización soterrada descuberta en 2012 ao ensanchar unha pista) e microtopónimos como A Ermidiña, A Cruz e Campo Dozón ou Campo do Ozón, o máis sorprendente. O nome desa aldea debía ser Laias. No século VI, baixo o rei suevo Teodomiro ponse en marcha a división parroquial, que tanta transcendencia tería en Galicia.
Encomenda de Beade
A partires do século X debeu organizarse o territorio ocupado pola parroquia, que recibiu un nome acorde cos seus grandes bosques. As institucións relixiosas comezan a intervir no espazo: A diócese de Lugo e as ordes relixiosas (mosteiros de Carboeiro, Aciveiro e Oseira). En 1106, en tempos de Xelmírez, aparece documentada a localidade de Viniola (Viñoa), ao lado do Asneiro. Outra institución de carácter relixioso que terá moita influenza en Soutolongo vai a ser a Encomenda de Beade, que pertencía á orde hospitalaria dos Cabaleiros de San Xoán de Xerusalén, fundada no século XI, a raíz das Cruzadas, para auxiliar aos peregrinos que acudían a Terra Santa. Presta servizos en Oriente e recada fondos en Occidente. En Galicia tiñan sete encomendas, unha en Beade (O Ribeiro, Ourense), no século XIII. Soutolongo convértese en priorato da Encomenda de Beade, que pretende controlar o incipiente comercio do viño do Ribeiro cara a Compostela, desde un enclave situado a carón do Camiño Real.
Nos séculos XII-XIII estableceuse en Des un centro de poder económico territorial en torno a unha mansión señorial que se transformaría nun dos pazos máis importantes da zona. Este señorío formado por "reserva" e "mansos" chegou a abarcar unha superficie de máis de 107 Ha., coñecida como Coto de Des. Abarcaba desde a Cruz do Seixo ata o Prado do Conde, localizado na gran terraza fluvial da Pontenova (río Asneiro).
O señorío de Soutolongo, coñecido popularmente como O Pazo, ocupou unha das zonas de mellor habitabilidade da parroquia, compartindo o lindeiro setentrional co Couto de Des. Aquí construiuse o pazo dos Infanzóns de Soutolongo de Arriba, que se extendía desde ata o Prado de Espinosa, a carón do río Asneiro. Nos séculos XV-XVI atopámonos cunha parroquia dominada por varios señoríos, que exercían un poder directo sobre os seus respectivos cotos e sobre as novas aldeas que se estaban formando como Eirexe e Vilar.
Outros señoríos eran os de Viñoa e Carracedo. Viñoa era un "territorio libre" que tardaría moito en incorporarse a Soutolongo. Aquí unicamente houbo dúas casas nobiliarias, a dos López e a dos Taboada, que chegaron a ter capela propia, como en case tódas as aldeas desta parroquia. A orixe de Carracedo estivo relacionada coa fidalguía; a casa máis antiga é a dos Novoa, evolucionada a partires dunha forma torreada contemporánea da vella oliveira, que a tradición oral data na época do descubrimento de América.
Pasaban por Soutolongo dous camiños reais (CR): O do Ribeiro cara a Santiago e o que enlazaba este co camiño real Ourense-Santiago, que transcorría por A Xesta. Aproveitando estes trazados, formouse unha rede viaria secundaria de acceso ás aldeas que se estaban formando. A encrucillada de Vistalegre era o centro neurálxico, o que propiciou a súa formación máis tardía, a mediados do XIX, a expensas dos señoríos situados cara o Leste (Des, O Pazo, Viñoa e Carracedo).
A Encomenda de Beade vai ter gran infuenza na vida social e relixiosa da parroquia a partires do XVII. O primeiro prior aparece en torno a 1534, tardando pouco en modificar a pequena igrexa que debeu ser construída entre os séculos XIII-XIV. As pinturas do interior do ábside, nas que aparece repetidamente a Cruz de Malta (de oito puntas en representación das boaventuranzas evanxélicas), corresponden á terminación das obras, en 1585.
