Los tambos eran construcciones destinadas al acopio de productos agrícolas, mercadería y al alojamiento de arrieros, comerciantes y viajeros. En 1548 este tambo acogió a Alonso de Mendoza quien había sido enviado para fundar la ciudad, cosa que hizo en el sector que actualmente ocupa la plaza que lleva su nombre.^[1]​ Tras la fundación se definió, de manera provisional, el sector como el destinado a los españoles, pero se respetaron las propiedades Irusta y Kirkincha o Quirquinchu, según diferentes crónicas. Tras la definición sobre la ubicación final del sector de españoles y la adjudicación de tierras a la Orden de San Francisco en 1549 se consolida la decisión de habitar la nueva ciudad,^[2]​ pero se replantea la división social y espacial, quedando el tambo indígena tras la frontera de los español y lo indígena. A fines del siglo XVIII, el tambo Quirquincho tenía cuatro patios,y era residencia y tambo a cargo del cacique Quirquincha,^[3]​ la zona en la que se inscribe el Tambo se halló entonces fuera del trazo principal de la ciudad, caracterizado por la cuadrícula conocida como damero y, tras el río, en el sector denominado Pueblo de Indios.

En 1792 Tadeo Diez de Medina y Mena compra el tambo por la cantidad de 20.010 pesos, en 1800 se instauró una Capellanía sobre esta propiedad.^[4]​ El tambo pasó por herencia a su nieta Vicenta Juariste Eguino quien la cedió a favor de Manuel Mirelles, viuda de su abuelo, a cambio de recibir la hacienda Pallina en Laja. Mirelles alquiló el tambo a Mariano Cárdenas por la suma de 1000 pesos anuales.^[5]​Cuando la viuda Mirelles falleció el tambo volvió a propiedad de Vicente Eguino, pero le fue confiscado a ésta como castigo por su participación en la Revolución de La Paz en 1809.^[6]​

Durante el Asedio de La Paz de 1811 el edificio fue quemado por los rebeldes indígenas cuando saqueaban el barrio de San Sebastián.

En 1880 se registra como un tambo de quinas y tabacos, posteriormente cumplió funciones diversas, entre las que se hallan: salón de bailes durante el Carnaval, pista de patinaje, Hospicio San José, y el Kinder Oscar Alfaro.

En 1954 parte del edificio fue entregado a la Cruz Roja Boliviana para que pueda instaurar la "cantina del lactante" y el "restaurante del niño", ambos con la finalidad de atender a hijos de madres trabajadoras en edad preescolar.^[7]​

Actualmente es un edificio municipal en el que se han implementado elementos arquitectónicos provenientes de diferentes edificaciones ya desaparecidas, sobre la plaza se aprecian puertas y ventanas características del periodo colonial, así como una portada de piedra extraída de la hoy demolida Casa de los Ayesta, que se encontraba en la esquina de las calles Sucre y Sanjinés.

El Tambo Quirquincho es una edificación de dos pisos con accesos desde la calle Evaristo Valle y desde la Plaza Alonso de Mendoza, alrededor del patio central se desarrollan los ambientes que actualmente sirven de oficinas administrativas y salas de exposición. Una de sus fachadas interiores presenta una arco del siglo XVIII en el que se encuentra esculpida la corona del rey de España, símbolo de los caciques indígenas reconocidos como autoridades legítimas por España. La otra fachada interior presenta una arquería de estilo barroco mestizo, rescatada del demolido Convento de las Concebidas, esta arquería fue donada a la ciudad en 1984 por el Arzobispado de La Paz.

El 20 de octubre de 1988 fue inaugurado como museo municipal y desde entonces acoge exposiciones temporales y permanentes así como eventos y actuaciones en su patio central.