Habitada desde tiempos remotos (Paleolítico inferior), su nombre parece proceder de la dominación romana, si bien aún no se han encontrado evidencias de esa época. Su apellido «de la Mata», alude a los montes de encinas o ‘matas’, que rodean su término, entre ellos el monte de La Andaya, que comparte con la villa de Lerma, y el de Rabé. En muchos de los dinteles de sus casas se pueden apreciar símbolos de la eternidad (estrellas de seis puntas) o cruces paganas cristianizadas, que representan ritos ancestrales que permanecieron en la memoria colectiva de sus habitantes, un ejemplo puede ser el apodo de «brujas», otorgado a las mozas del pueblo, aunque no existe constancia de procesos inquisitoriales. El primer testimonio documental se remonta al año de 1242, mientras que sus ordenanzas datan de 1558, anteriores incluso a las de la villa de Lerma.

Durante toda su historia tuvo particular importancia en su economía la uva, estando actualmente adscrita a la Denominación de Origen Ribera del Arlanza. Fruto de esta importancia, los trece lagares con que llegó a contar el pueblo a principio del siglo XX, y de los que hoy a duras penas se mantienen dos o tres en pie. Cada lagar llevaba un nombre característico, generalmente aludiendo a su mayor propietario, como el de Dios, el de los Calvos, el del Maestro, el de Marín, el de Pacho, el de las Bombas…

Quintanilla tuvo una gran importancia en la construcción del Palacio del Duque de Lerma (1603-1618), valido del rey Felipe IV, pues se necesitó una gran cantidad de materiales, quedando patente en la documentación que buena parte de las piedras procedieron de la cantera de los Calazares, mientras que las baldosas y tejas se cocieron en su mayoría en el antiguo horno o tejera, ubicado junto a la actual panadería.

Posteriormente, Quintanilla fue el escenario de las andanzas del cura Merino durante la Guerra de la Independencia contra el invasor francés (1808-1812). Se da la circunstancia de que Jerónimo Merino y Cob procedía del vecino Villoviado, y en esta zona hostigó repetidamente a las tropas francesas, que tenían paso obligado por Quintanilla por el denominado ‘Camino Real’, atribuyendo a una de estas escaramuzas el incendio del Mesón de la Venta, en el límite del camino entre Quintanilla, Rabé y Fontioso. Son muchas las historias que aún se escuchan de soldados franceses enterrados en bodegas. También las guerras carlistas del XIX tuvieron su escenario en esta comarca, quedando constancia de la presencia del general carlista Zaratiegui hacia 1837.