To correctly classify EEG with different mental tasks, a new learning algorithm for Evolving Cascade Neural Networks (ECNNs) is described to avoid over-fitting of a neural network due to noise and redundant features. The learning algorithm calculates the value of a fitness function on validate set and accordingly updates the connection weights on training set. The learning algorithm uses the regularity criterion for selecting the neurons with relevant connection. If the value Cr calculated for the rth neuron is less than the value Cr-1 calculated for the previous (r-1) neuron, the features that feed the rth neuron are relevant, else they are irrelevant. An ECNN starts to learn with one input node and then, adding new inputs as well as new hidden neurons, evolves it. The trained ECNN has a nearly minimal number of input and hidden neurons as well as connections. The algorithm is applied to classify EEG with two mental tasks. The trained ECNN has correctly classified 83.1% of the testing segments. It shows a better result, compared with a standard BP network.