Dokładna data budowy kościoła nie jest znana.
Jego potwierdzenie znajdujemy w dokumentach z początku XIV wieku lecz zapewne istniał już wcześniej. Najstarszą część kościoła stanowi obecnie prezbiterium.
Kościół o konstrukcji halowej został zbudowany z cegły i miejscowego czerwonego piaskowca.
W XV wieku do południowej ściany dobudowano kaplicę św. Anny.
Na początku XVII wieku dobudowano kruchtę oraz renesansową kaplicę Loretańską. W jej podziemiach znajduje się krypta z grobem fundatora, bogatego olkuskiego mieszczanina - Stanisława Amendy.
Stojąca obok kościoła neogotycka dzwonnica została zbudowana na początku XX wieku.

We wnętrzu kościoła na szczególną uwagę zasługują:

- Ołtarz - poliptyk z końca XV wieku stanowiący wybitne dzieło sztuki gotyckiej malarzy krakowskich Jana Wielkiego i Stanisława Starego,

- Wielki Ołtarz - renesansowy z początku XVII wieku z obrazem Świętego Andrzeja, patrona Kościoła,

- Ołtarz Świętego Jana Kantego - ołtarz późnobarokowy z drugiej połowy XVII wieku z zamieszczonym centralnie obrazem postaci Świętego Jana Kantego,

- Chrzcielnica - pochodzi z końca XVI w., okazała, wykonana w formie romańskiego kielicha, odlana z olkuskiego ołowiu,

- Ambona z początku XVII wieku stanowiąca kompozycyjną całość z organami i ołtarzem wielkim,

- Średniowieczne , renesansowe i barokowe stalle gwareckie oraz wiele płyt epitafialnych,

- Krzyż Gwarków - wykonany z olkuskiego srebra, okazały, pochodzący z XVII w., będący darem olkuskich gwarków,

- Późnorenesansowe Organy - są jednym z najcenniejszych zabytków olkuskiego kościoła pw. św. Andrzeja. Ich historia sięga 1611 roku, kiedy podpisano umowę na wykonanie instrumentu z Hansem Hummlem, wybitnym organomistrzem niemieckim mieszkającym w Krakowie. Po śmierci syna, który zginął podczas budowy instrumentu, Hummel opuścił Olkusz. Budowy organów dokończył jego uczeń, Jerzy Nitrowski.
Długoletnia konserwacja organów zakończona w 1992 roku przywróciła im dawną świetność. Instrument posiada dwa manuały (klawiatury ręczne), pedał (klawiaturę nożną) i 31 głosów. Olkuskie organy mistrza Hummla przedstawiają szczególną wartość, zachowały oryginalny mechanizm i znaczną większość spośród 1776 piszczałek (dzięki temu jest on jednym z najciekawszych zabytków sztuki organowej w Polsce). Te głosy, które uległy przeróbce, zostały wiernie zrekonstruowane według zachowanych wzorów. Aby uzyskać jak najwierniejsze brzmienie zdecydowano się na strojenie organów w obowiązującym w połowie XVII wieku stroju nierównomiernie temperowanym. Dlatego na olkuskim instrumencie można wykonywać tylko muzykę renesansową i wczesnobarokową.
Co roku, jesienią organizowane w mieście Olkuskie Dni Muzyki Organowej, przyciągają melomanów z całej Polski.