Side-channel attacks (SCA) can obtain secret information related to the private key used during encryption executed on some device by exploiting leakage in power traces produced by the device. In recent years, researchers found that a neural network (NN) can be employed to execute a powerful profiled SCA, even on targets protected with countermeasures. This paper explores the effectiveness of (1) utilising a genetic algorithm (GA) to train the weights of NNs used for SCA, (2) using NeuroEvolution of Augmenting Topologies (NEAT), which is a commonly used approach for automated NN architecture search, to construct architectures for use in SCA, and (3) \textit{Neuroevolution to Attack Side-Channel Traces Yielding Convolutional Neural Networks} (NASCTY-CNNs), a novel GA that applies genetic operators on the scale of layers rather than neurons to automatically produce CNNs for side-channel analysis. The results indicate that weight evolution and our neat-based approach are successful when attacking weak, unprotected targets. However, they do not perform well on the ASCAD data set, against which SCA methods are commonly benchmarked, suggesting these methods require significant tweaking to be effective. NASCTY can automatically produce novel NNs that achieve performance close to state-of-the-art approaches on both masked and desynchronised ASCAD traces, demonstrating that such neuroevolution methods provide a solid venue for further research.