Según el cronista Bernabé Cobo, la posible ubicación habría sido el antiguo Palacio de Coracora: .
El año siguiente ya se deja constancia que la edificación había sido levantada: .
Asimismo se toma en cuenta que en el siglo XVI aún no se había construido la Casa de Moneda, en el solar que hoy ocupa el edificio del Hotel de Turistas del Cusco, y que tanto la Plaza Regocijo como la Plazoleta Espinar y el espacio ocupado por ese solar formaban todas un solo espacio público (la Plaza de Tlanguiz).
En 1840, durante la guerra contra la Confederación Perú-Boliviana, el general Agustín Gamarra demolió a cañonazos el Convento de los Agustinos con lo que muchos de sus elementos líticos fueron utilizados en el Palacio del Cabildo.
Esta adecuación terminó de realizarse hacia el año 1848, fecha que aparece grabada en el frontis del palacio.