El seu nom original era el de Santa Coloma de Montpedrós, en relació a la muntanya que s'alça al seu costat i en el cim de la qual estava l'antic castell, conegut com Castellnou de Cervelló. És a partir del segle XIV, quan comença a aparèixer documentada amb el nom de Santa Coloma de Cervelló.

La primera notícia que ens ha arribat data de l'any 1026. És en aquest segle que es construeix l'edifici, que a finals del segle XVI va ser profundament reformat.

Sembla ser que l'estructura de la nau podria correspondre a la d'època romànica, si bé va ser ampliada per l'est, eliminant la capçalera, i afegint capelles laterals.

L'element més visible des de l'exterior de la fàbrica romànica és el mur oest, on s'obre una finestra en forma de creu. Els dos grans òculs van ser oberts amb posterioritat.

També és del segle XI gran part de la torre de campanar, tot i que ha estat molt modificada. Destaquen els grans carreus vermellosos en les cantonades.

Cal entrar a dins de la sagristia per poder observar l'altre element romànic que es conserva. En aquest cas és l'antiga absidiola sud, que havia quedat oculta amb les reformes del segle XVI i que va ser descoberta en 1988. Té planta semicircular i una petita finestra en la part central. Actualment té una gran obertura en forma de porta. La teulada i la part superior van ser reconstruïdes, tot i que la volta és encara l'original.