Legal or not?
This question cannot be answered in one sentence. Not every BASE jump is illegal, and not every BASE jump is done with permission. Both are done daily, somewhere around the world. The situation differs from country to country. Jumps from cliffs might be tolerated somewhere, but you will perhaps never get permission to jump from a bridge there, due to different reasons (mostly questions of insurance). In some countries, BASE jumping falls under the jurisdiction of the same regional body that governs skydiving, while in other countries, low altitude jumpers are not administrated by any “official” organisation. Therefore, BASE jumping is not illegal in and of itself. In most countries, you will need permission from the owner of an object from which you want to leap, as well as permission from the owner of the area where you will land. Usually, they require an insurance from you, which covers their costs or costs of a third party that might be involved in any way. Each country has its own system of aviation laws and insurance rules, therefore it is very hard to define an overall answer.
If you intend to do a less-than-legal-jump, you should think twice about what could happen. For example, trespassing in some states of the US is a very dangerous thing, sometimes more dangerous than jumping a fixed object. In the event that you get injured, or you damage something, an unpermitted jump could cost you a lot more than you can probably afford. Usually, insurances only cover costs from official activities.