In this paper, the user selection problem is investigated in the multi-user satellite multiple-input multiple-output (MIMO) downlink, which includes a multi-beam geostationary earth orbit (GEO) satellite in space and multiple terrestrial users on the ground. Considering that the number of users is much larger than that of beams or feeds, user selection should be performed so that multiple users can be served successively in different time slots. In order to meet the quality of service (QoS) requirements of users and maximize the system sum rate, three user selection algorithms are proposed: greedy user selection (GUS) algorithm, add swap user selection (AS) algorithm, and random add swap user selection (RAS) algorithm. Among the three algorithms, only the “add” operation is adopted in the GUS algorithm, both the “add”, and “swap” operations are considered in the AS algorithm. On this basis, heuristic search and “random swap” operation are introduced and the RAS algorithm is obtained. The complexity of the above three algorithms is analyzed analytically and the RAS algorithm is found to have the highest complexity. Besides, the performance of the three algorithms is analyzed and compared through simulations, where the random user selection (RUS) algorithm is taken as a benchmark. Numerical results show that the system sum rate and energy efficiency are greatly improved by the proposed algorithms and the RAS algorithm has the best performance.