Como en todos los pueblos de la zona, los historiadores remontan el origen de Canencia a la repoblación segoviana de la Sierra tras la conquista de Toledo por Alfonso VI en 1085. Pero restos de enterramientos, encontrados al construir la vía férrea Madrid-Burgos, hacen pensar en asentamientos anteriores de los que no hay ningún dato fiable.
Algunos textos acreditan la existencia de la población en la Baja Edad Media y la utilización de su territorio y caserío para la realización de cacerías reales. Se dice incluso que en Canencia se localizaron las perreras del monarca, de donde podría derivarse el nombre del pueblo.
Hasta su incorporación a la provincia de Madrid, en 1813, Canencia era un lugar de realengo adscrito a la Comunidad de Ciudad y Tierra de Segovia, cuyo régimen la mantenía eximida de la mayoría de las servidumbres feudales. Como todos los pueblos del Valle del Lozoya, su desarrollo histórico estuvo muy vinculado a la Cartuja de El Paular.
A mediados del siglo XVIII, la organización jurídica teritorial seguía siendo la misma. Habitaban el pueblo 187 vecinos, incluidas 27 viudas, todos ellos viviendo en el núcleo, ya que no existían granjas ni alquerías. Se componía de 232 casas bajas y habitables, incluidas las del Concejo. Contaba con tierras de regadío y secano, prados, eras, pozas y dehesa boyal. También con cuatro molinos harineros y 28 colmenas. El ganado era vacuno, mular, caballar, de cerda, lanar merino trashumante y cabrío. Entre los establecimientos se contabilizaban una taberna, una abacería y carnicería, un mesón, un hospital destinado a pobres transeúntes y una herrería.
En la mitad del siglo XIX, ya integrado en la provincia de Madrid como municipio independiente, Canencia se había convertido en un núcleo de cierta importancia, alcanzándose los 700 habitantes y las 300 casas. Contaban, además de con Ayuntamiento y cárcel, con una escuela primaria a la que asistían 80 niños.
Durante la Guerra Civil, Canencia fue un lugar de retaguardia para las tropas que luchaban en el cercano frente del Macizo de Peñalara. Se perdió casi todo el patrimonio eclesiástico, pero el resto de los edificios no fue afectado.
Los primeros servicios públicos e infraestructuras se empezaron a implantar entre 1941 y 1954: agua corriente en los domicilios, alumbrado, mejora de las carreteras. En esta época se acabó la carretera del Puerto de Canencia que conduce al pueblo de Miraflores de la Sierra. En 1943 se construyó el nuevo Ayuntamiento, en 1950 la nueva escuela y en 1958 llegó el teléfono.