Many novelties are due to Paleolithic (500.000-8.000 b.C.): several rough sculptures, some tools and, most important, rock painting in caves. We can set a concret area in Spain: the franco-cantabric one, where cave of Altamira, (Santillana del Mar, Cantabria) stands out as a true jewel of "rock art". Its beatiful paintings were made in domestic caves where persons lived and got protection.
There are many caves in Cantabria and Asturias: many days might be taken for visiting all of them in spite of its proximity to each other.
Bisontes en Altamira
Bisons in Altamira.
We do remark:

Far from Cantabric area other places must be mentioned:
Abrigo de Bicorp
Deer in the Shelter of Bicorp.

Many paintings in Levante area were made at Mesolithic(8.000-4.000 b.C.). They were usually outwardly painted; therefore they get to do with minor "primitive architecture".
The most important between the many instances of this area could be the Caves-shelter of Alpera in Albacete, the Caves-shelter of Macizo del Caroig, and, specially, those of Bicorp in Valencia.