In this work, the problem of data security in cloud data storage is investigated. For this purpose, an effective and hybrid distributed scheme, namely, Parallel Genetic based Secure Data Storage Model (PGSDSM) is proposed. The optimal computing nodes are selected and keys are generated in a heterogeneous cloud environment by using Parallel Genetic Algorithm (PGA). Hence, the crossover, mutation and selection operators are used to calculate the best fitness value. The distributed function evaluation is one of the successful applications of PGA. The parallelization of fitness evaluation is done by assigning a fraction of the population to each of the computing nodes. PGA is not only the extension of traditional Genetic Algorithm (GA), it represents a new class of algorithms and searches the space of solutions differently. In many cases, PGA provides better performance than the single population based algorithms and it reduces the time and number of function evaluations to locate a solution. Advanced Encryption Standard (AES) algorithm is employed to perform the encryption and decryption processes.