Se conocen muchas leyendas sobre esta Virgen, aunque la más conocida cuenta cuando dos leñadores se disponían a cortar un majestuoso y robusto árbol, encontraron en medio del tronco la imagen de la Virgen María.

Cotoca probablemente nació como una población pequeña formada espontáneamente por agricultores que habitaban las praderas de la zona, en donde como puntos blancos en medio de la llanura surgen pueblitos y caseríos como Paurito, Pailas, Tarope y otros.

Cotoca fue en tiempos pasados pascana obligada de los viajeros a la Chiquitanía y al Brasil y estuvo muy cerca del lugar a donde se trasladó por segunda vez la ciudad de Santa Cruz, "la Vieja".

Al morir doña Elvira Barroso, el hijo y el viudo entregaron la imagen a un rico ganadero, don Manuel Redentor Roca, quien le construyó el primer velatorio.

La Virgen llegó a ser tan famosa por sus milagros que en 1799 el Deán Toledo Pimentel solicitó licencia al obispo Ochoa, residente en Punata, para la construcción de una parroquia rural.

Como se puede observar, la leyenda relatada por Aquiles Gómez, guarda cierta afinidad con el documento aunque también hay diferencias.

La obra fue trabajada con adobes y la dirigió el padre Meleán, quien años más tarde murió en Tarata.

El religioso Fray Camilo de Agrazar decoró los interiores del templo; correspondiéndole al cura Zacarías Céspedes construir la casa parroquial.