La Collegiata di Sant'Andrea è sorta insieme alla fortezza di Montecarlo, tra il 1342 ed il '34, con lo stesso nome della chiesa di Vivinaia, distrutta dai Fiorentini insieme all'antico borgo. Della chiesa rileva anche il fonte battesimale, ma rimane comunque sottoposta all'autorità della pieve di San Piero in Campo fino al 1408.

Il concepimento della collegiata, nella sua architettutra originale, rispecchia le esigenze di Monecarlo, borgo fortificato che sorge a scopi prettamente militari. La parte inferiore della facciata, quella originaria, è perciò piuttosto bassa. Essendo comunque fin da subito l'edificio più alto del borgo, viene anche emanato un editto che vieta a qualsiasi cittadino di arrampicarsi sul tetto, da dove sarebbe stato possibile spiare il castello al suo interno. Per le stesse ragioni il campanile della chiese viene realizzato in modo che la sua altezza non superi quella del tetto. Verrà poi innalzato alla sua attuale statura nel 1903.
Della struttura originale non restano molti elementi a disposizione. Si è però ben conservata la cripta, che in passato è stata la sede delle riunioni della Compagnia della Madonna del Soccorso. La confraternita l'ha scelta anche come luogo di sepoltura dei suoi adepti. In realtà la cripta, in seguito, era stata affrescata, ma i lavori sono stati poi tolti e collocati nel Museo Parrocchiale di Montecarlo. Oltre alle tombe dei membri della confraternita, sono sepolti nella cripta altri due illustri cittadini della città: Felice Seghieri, vescovo di Sovana e Pitigliano morto prematuramente nel 1759, e Jacopo Bianchi, uno dei finanziatori delle opere all'interno della chiesa.
Nei secoli successivi alla nascita della Collegiata si sono susseguiti molti lavori di ampliamento, ristrutturazione ed abbellimento. Risalgono al XVI secolo la collocazione del nuovo fonte battesimale, delle acquasantiere, dell'altare della Concezione (1597), gli affreschi (oggi rimossi) della cripta e varie altre opere di decorazione. Nel Seicento sono stati effettuati ulteriori abbellimenti ed aggiunte alcune delle tele ad olio della sagrestia.
Nel XVIII secolo sono stati avviati lavori molto imponenti, come la ristrutturazione della chiesa, nel 1783, diretta dall'architetto Giuseppe Vannetti e dall'ingegnere Giuseppe Bernardi. È dello stesso periodo il grande affresco, oggi anch'esso portato via dalla Collegiata, che rappresenta l'Ultima Cena. Si tratta di un'opera molto insolita e particolare, che ha la peculiare caratteristica di essere dipinta ad olio. Le stuccature dei pilastri e gli affreschi della cupola sono stati effettuati nell'Ottocento.