Halibut has historically held notable cultural and symbolic significance for northern coastal communities. Its prominence is also evident in Norwegian prehistoric rock art, indicating a longstanding special relationship between humans and halibut. This study provides an indepth examination of halibut representations in Norwegian hunter-fisher-gatherer rock art, found at 15 sites along the coastline, with most depictions dating from 6800 to 3000 BP. By comparing these depictions with ethnographic data from Norway and North America, this analysis offers valuable insights into early halibut fishing. The study suggests that prehistoric halibut fishing was a prestigious, male-dominated activity intertwined with rituals, taboos, and beliefs concerning luck, fertility, and respect for the halibut. Furthermore, the connection between halibut and cervids in rock art points to a refined observation and profound understanding of species-specific seasonal patterns and their interrelatedness, providing important perspectives for interpreting rock art and prehistoric human-animal and human-environmental relationships in the north.