El origen de los Kolla se remontaría a la etapa final del Imperio de Tiwanaku a orillas del lago Titicaca, en Bolivia, donde existían aproximadamente doce señoríos independientes aymara-hablantes en pugna. Entre ellos sobresale el señorío Kolla ubicado en un extenso territorio en las riberas nor-oriente y sur-poniente del lago. Estaba constituido por dos unidades étnicas en pugna: los Kolla, que tenían acceso al poder político; y los Puquina, que correspondían a la antigua población nativa del área.
Durante el siglo XV este señorío fue invadido por el Inca Wiracocha o Pachacuti . Luego se produjo una gran rebelión kolla que fue aplastada por el Inca Tupac Yupanqui, incorporando a los alzados como tropas de choque en la conquista de otros territorios. Así segmentos importantes de kollas fueron trasladados a territorios cercanos o lejanos en calidad de encomendados. Es el caso de los kollas del noroeste argentino, muchos de los cuales fueron destinados al trabajo minero. Los Kolla actuales reconocen ser descendientes de ellos.