Before Notre Dame
When everyone in Paris decided (or were forced) to become Christians, about 400 AD, they didn't need the old temple anymore, and instead the Merovingian king Childebert built a "magnificent church" (according to Gregory of Tours) in 528 AD. Childebert's church was dedicated to Saint Stephen. Not much is left of this church, though, because the bishop Maurice de Sully had it torn down in 1160 to build the new church of Notre Dame, which is still there today.
Learn by doing: watch a building being torn down
More about Notre Dame of Paris