Los testimonios de mayor antiguedad corresponden al Neolítico; se trata de los túmulos, de los que encontramos ejemplares en la zona sur del municipio; concretamente en la Bobia se han documentado un dólmen y dos túmulos que forman parte del total de 87 catalogados en la comarca. No obtante, Vegadeo sí cuenta con referentes de las tribus que poblaban el Eo, tales como Pésicos, Egobarros y Albiones; de éstos últimos ha quedado la estela de Nícer Clutosi, dedicada a uno de los Albiones, que se encuentra en el museo Arqueológico de Asturias y que apareció en el lugar de A corredoira en el año 1932: se trata de una estela de carácter funerario dedicada a Nícer, en el primer siglo de nuestra era. Este hallazgo da cuenta de la existencia en el área de los Albiones, pueblo que convivió con la dominación romana y tuvo su plaza fuerte en la zona.

En el ámbito de la cultura castreña, Vegadeo cuenta con nueve poblados documentados que se concentran en la franja oriental del municipio: Penzol, Castromourán, Meredo, Molexón, Montouto, Viladaelle, La Abraira y dos asentamientos en la parroquia de Abres, al noroeste. Estos poblados subsisten y se amplían con la llegada de Roma, en busca del preciado oro de la comarca. De época castreña, queda para Vegadeo el honor de haber aportado una de las máss importantes joyas de esta etapa; es la Diadema de Vegadeo, pieza de oro rematada en sus laterales por dos anillas que sirven para ceñirla, realizada entre los siglos V y I a.C.; hoy se encuentra en el museo Arqueológico Nacional y un segundo fragmento en el Museo Lázaro Galdiano, ambos en Madrid.

La historia medieval de Vegadeo comienza en las Cortes de Salamanca celebradas en el año 1154 bajo la dirección del Rey Alfonso VII. En esta sesión se dona al entonces Obispo de Oviedo, Martín, la tierra de Ribadeo, ubicada entre los ríos Eo y Navia, conocida entonces como Honor del Suarón. En 1280 nacerá Castropol de la mano de la puebla de Reboredo, que pronto comenzaría a tener enfrentamientos con el Obispo, hasta que en 1584 el vecindario compra el derecho a organizarse en concejo dentro del cual estaba Vegadeo (Vega de Ribadeo en aquellas fechas), que era uno de los partidos en que se estructuraba el de Castropol y cuya capital se hallaba en Piantón. No será hasta 1834 el momento de la ansiada independencia; en ese año, Vega de Ribadeo se convierte en concejo y unos años más tarde se inicia la construcción del actual edificio municipal. 1854 será el año de la construcción de la Iglesia Parroquial. Quedaba un paso por dar y en el mes de febrero de 1916 una Real Orden le concederá el actual nombre de Vegadeo.