To see the effectiveness and optimization of the routing algorithm in MSS network with the minimum delay and to improve the performance of the QoS via satellite, a new routing algorithm using genetic algorithm is proposed in this paper. The bit strings of the chromosome (individuals) structure in the genetic algorithm are determined as the number of links in networks and provide the availability of the link. The format of the bit string will be changed for every traffic intensity condition at each time interval. The individuals are evaluated and correspond to the link allocated at the update time, thus, the routing is guaranteed to be successful. The fitness function is defined to minimize the link requirement to obtain QoS performance. The interpolation between the best and the worst Pareto rank is then examined for each fitness value. For a simulation model, a system is designed for network topology that consists of satellite network and terrestrial network. The satellite network is assumed to be Iridium constellation with 66 satellites and the terrestrial network consist of 28 earth stations. The sending data is generated by transport agent and its supported by the higher application layer as a traffic generator. The performance evaluation of the genetic routing algorithm is proposed for throughput of the system. The results show that the throughput for the genetic routing algorithm is higher than the conventional algorithm.