De los primeros tiempos de Colmenarejo no hay muchos datos claros. Distintas versiones han llegado a nuestras manos sobre su fundación y el origen de su nombre. Marín Pérez lo sitúa en el siglo XI y atribuye el topónimo a la existencia en la zona de numerosas colmenas. Las Transcripciones Lorenzanas afirman que fue fundado en 1140 después de la fundación de la villa de Colmenar Viejo y que de su diminutivo tomó la denominación. El origen del núcleo está relacionado con la vocación ganadera de los segovianos, la cual hace que se adentren a la sierra de Guadarrama en dirección sur en busca de pastos para el ganado, creando posadas y cabañas de pastores junto a la Cañada Real de Las Merinas y la Cañada Real Segoviana. A partir de este núcleo, denominado en documentos medievales «Colmenar de Don Mateo» se creó un núcleo de población que, por su dimensión reducida en relación a Colmenar Viejo, comenzó a denominarse Colmenarejo.

Sea cual fuera su origen, los primeros documentos históricos datan del siglo XIII. Colmenarejo perteneció alternativamente a Segovia y Madrid. En 1208 pertenecía al Sexmo de Manzanares que entonces era de Segovia. En 1287, una sentencia del rey Sancho IV «El Bravo» lo sigue adjudicando a Segovia pero este mismo monarca en 1294 otorga este territorio al Concejo de Madrid hasta que en 1312 el rey Fernando IV incluye en tierras segovianas, el Sexmo de Manzanares, en donde Colmenarejo se hallaba incluido.

A lo largo del siglo XIV, los diferentes monarcas comienzan a hacer concesiones territoriales a la nobleza, convirtiendo estos lugares en tierras de señorío y es en 1445 cuando la familia Mendoza adquiere el título de propiedad y la jurisdicción plena de señorío de todo el Real Manzanares.

El único hecho destacable en el siglo XVI, por su importancia para el lugar, fue la segregación de la iglesia de Colmenarejo de la parroquia de Galapagar, por Breve de Pío IV y a instancias de Felipe II, quien devoto de Santiago Apóstol, paraba a escuchar misa en su camino hacia el monasterio de San Lorenzo de El Escorial.

En 1630 Colmenarejo adquiere el título de villazgo que supuso la independencia de la vecina localidad de Galapagar. A mediados del siglo XVIII y de acuerdo con el Catastro de Ensenada de 1751, Colmenarejo contaba con 59 vecinos que habitaban dentro del casco urbano y se dedicaban básicamente a labores agrícolas y ganaderas. El carboneo y la extracción de granito formaban parte también de las actividades de los lugareños.

Es la presencia de colmenares la que influye en el topónimo de la localidad, propiciada por las bondades climatológicas: se registran en el Catastro hasta 231 colmenas, por lo que la producción de miel y su comercialización debía ser notoria en la comarca.

La extracción de cobre también constituyó una fuente de riqueza en el municipio como muestra numerosos vestigios de la explotación minera en la Casa de la Fundición y la Casa de las Minas. El puente herreriano del Tercio, hoy sumergido bajo las aguas del embalse de Valmayor fue construido con motivo del tránsito habitual de monarcas y sus cortes hacia el Monasterio de San Lorenzo de El Escorial. También del s.XVIII datan posiblemente las llamadas Fuente del Navazo y Fuente del Pozuelo, lugares donde tradicionalmente las gentes acudían a coger agua para uso doméstico. El siglo XIX se abre a Colmenarejo con la supresión de los señoríos decretada en 1811 por las Cortes de Cádiz , consecuencia directa de la Guerra de la Independencia contra el invasor francés.

En 1833, de acuerdo con la nueva distribución administrativa de España, Colmenarejo pasa a integrarse en la provincia de Madrid. A finales del s. XIX y principios del s. XX empiezan a construirse las primeras villas de veraneantes como resultado de las corrientes que revalorizaban el contacto con la naturaleza que difundió la Institución Libre de Enseñanza que provocará a lo largo del s. XX un despegue económico.