A colony (known as a base until the Avalon Hill edition) is a group of one player's ships on a single planet. A colony on a player's own planet is called a home colony, and a colony on another player's planet is called a foreign colony. Each player starts with one home colony on each of his or her planets. The game is won once one or more players gain five foreign colonies. If a player has two or fewer home colonies, he or she cannot use his or her alien power.

In the FFG edition and in Cosmic Encounter Online, rules for a shortened game are included. Players begin with only four home planets, and the game is won by the first player(s) to claim a fourth foreign colony. In this version, players lose their alien power if they control one or fewer home colonies.