The archaeological record of the European Neolithic is marked by thousands of megalithic monuments of varied styles. Patterns in the orientation of similar megaliths betray a deliberate intent in their construction that can, in some cases, be related to topographic features or celestial events of prominence in the cosmology of their builders. This talk will introduce the field and methodologies of archaeo-astronomy, as complementary to other archaeological approaches. It will then apply them to the specific case of the megalithic structures built in Northwest Iberia during the Mid to Late Neolithic (c. 4000 cal BC). Focusing first on a cluster of passage graves in Carregal do Sal (central Portugal), a pattern in orientation is identified relating the structures to both a conspicuous mountain range on the horizon and the red star Aldebaran that would rise above it. This, it is suggested, marked the time for these Neolithic pastoralists to move to the mountain range, “following the star”. Toponymic folktales that tell similar stories are also considered. Finally, other megalithic clusters in north Portugal are also discussed, and the potential role played by such Neolithic stars discussed.