You cannot be part of a religion if you are going to start a new one.
The initial cost is 300 gold, and it builds a Small Temple in the region.
This number varies, I believe. I think I've seen 300, but I also believe I've seen 450 and maybe even 500 gold as a requirement.