Con la disolución del Imperio Romano de Occidente en el 476 y los visigodos ya asentados en la Península Ibérica, estos terminan imponiéndose en el territorio a los hasta entonces indestructibles romanos. No existen numerosos restos arqueológicos de época visigoda y de la Alta Edad Media, aunque podemos destacar la existencia de una necrópolis en el Cerro de San Juan en Valdevacas y Guijar, muy próximo a la villa romana, que pudo pertenecer a un antiguo poblado visigodo.
Tras la invasión musulmana en el 711, cabe pensar que estas tierras se quedaron vacías de población, permaneciendo como una zona de frontera entre cristianos y musulmanes hasta el siglo XI. Tradicionalmente se ha afirmado que Abderramán III residió por un breve periodo de tiempo en una fortaleza de la Villa de Pedraza de mediados del siglo VIII. Quizá, coincidiendo con su derrota en la batalla de Simancas (939).
Hasta el reinado de Alfonso VI y tras la toma de Toledo en 1085, no se integrarán los territorios de la Comunidad en el reino de Castilla y León. Es en este momento en el que se les empieza a dotar de organización territorial y de fueros con el objetivo de atraer población.
A pesar de que no existen testimonios escritos sobre el origen de la Comunidad de Villa y Tierra de Pedraza, es posible que surgiera entre los siglos XI y XII, como ocurre con la de Sepúlveda. En un inicio, los territorios de Pedraza estuvieron bajo la jurisdicción de la Villa de Sepúlveda, cuyos dominios se extendían hasta el valle del río Pirón, quedando confirmado en el Fuero Viejo de esta Villa del año 1076 por el rey Alfonso VI. En una bula del papa Calixto III del año 1123, Pedraza ya aparece como alfoz independiente de Sepúlveda, pudiéndose probar gracias al diploma de Alfonso VIII del año 1208, donde se recogen los límites de la Tierra de Segovia. No es de extrañar que el establecimiento de fronteras entre las dos Villas fuera objeto de numerosas disputas durante algún tiempo.
Las Comunidades de Villa y Tierra de la Extremadura castellanas se regían con independencia las unas de las otras y compartían una serie de características: gozaban de autonomía y de un mismo rango; poseían un amplio territorio; estaban sometidas únicamente al Rey; tenían plenas facultades gubernativas, fiscales, judiciales y militares sobre la población del alfoz; y por último, se encargaban de la ordenación y defensa de su territorio.
En la Comunidad de Villa y Tierra de Pedraza las aldeas del alfoz se agrupaban en torno a los Concejos, que gozaban de cierta autonomía, y estos a su vez se congregaban conformando la Comunidad. Cada Concejo estaba dirigido por un "iudex" o Justicia, nombrado por el rey, que se encargaba de la jefatura política de la localidad, lo que le otorgaba la potestad para convocar las Asambleas Vecinales, el órgano de gobierno de los Concejos, y a las que podían asistir todos los vecinos. Estas asambleas se solían celebrar en los pórticos de las iglesias románicas, como en el de la Ermita de Nuestra Señora de las Vegas.
Sin embargo, los intereses de la Comunidad se regían desde la Villa de Pedraza, que servía como núcleo defensivo en los momentos de mayor peligro, acogiendo a la población del alfoz cuando era necesario. También actuaba como centro de organización interna, dotando de cohesión a la población mediante el desarrollo de una entidad jurídica y una mentalidad común.
Desde el inicio de la repoblación la ganadería se convirtió en la actividad principal de la comunidad, gracias a la riqueza de pastos y a que las tierras eran poco aptas para la agricultura.
