Well, you're a little off. St. Constantine legalized Christianity, supported the Church (by among other things calling Nicaea to straighten out the row the Alexandrian presbyter Arius had provoked with his teaching that Christ in not God), and built his capital of New Rome (soon renamed Constantinople) without pagan temples, and with churches, but he hardly proclaimed Christianity as the religion of the Empire.
The Senate, still pagan, voted him divine honors upon his death (though he had been baptized shortly before by an Arian priest). (Amusing quiz question: which Roman god 1. was real, 2. is venerated as a saint by Christians east and west? A: Constantine the Great.)
It was a much later Emperor Theodosius, who eventually made Christianity the Imperial state religion and actually outlawed paganism.
Now you went and spoiled my weekend :-) but thanks for clarifying that. I should have said he "legalized" Christianity.