Wind energy is increasingly applied as a large scale clean energy generating alternative to fossil fuels. However, limited amount of real wind data results in inaccurate construction of Wind Frequency Maps (WFMs), which model the stochastic nature of wind. The inaccuracies in WFMs may lead to over or under estimation of wind power eventually causing significant losses to wind-farmers. Hence, to resolve this crisis, deep generative models such as convolutional Variational Autoencoders (VAEs) are implemented in this work to enable accurate construction of WFMs from limited amount of real wind characteristics data. However, the heuristics based estimation of hyper-parameters in VAEs decrease their efficiency. Thus, in this work, a novel multi-objective evolutionary neural architecture search (NAS) strategy is devised for simultaneously estimating the optimal number of convolutional and feedforward layers, number of filters/nodes in each layer, filter size, pooling option and nonlinear activation choice in VAEs. The proposed framework is designed to balance the conflicting objectives of generalizability and parsimony in VAEs, thereby reducing the chances of their over-fitting. The optimally designed VAE (with 92% accuracy) is used to generate new wind frequency scenarios for accurate construction of WFM. Additionally, the effect of number of new scenarios required for accurate WFM construction is also studied while performing the comparison with an ideal case. It was found that WFM constructed with original limited data resulted in 9% deficit in energy calculation from a single wind turbine, justifying the need for generative models such as VAEs for accurate wind characteristics modelling. © 2020 IEEE.