Organisms often modify their environments to their advantage through a process of niche construction. Environments that are improved through positive niche construction can be viewed as a public good. If free riders appear that do not contribute to the shared resource and therefore do not incur any associated costs, the constructed niche may become degraded resulting in a tragedy of the commons and the extinction of niche constructors. Niche construction can persist if free riders are excluded, for example if niche constructors monopolise the resource they produce to a sufficient degree. We suggest, however, that the problem of free riders remains because it is possible that non-niche constructors with an enhanced ability to access the resource appear and invade a population of constructors. Using mathematical models we show that positive niche construction can be maintained if it is inextricably linked to a mechanism that makes free riding costly, such as a trait that confers a benefit to only niche constructors. We discuss this finding in terms of genetic interactions and illustrate the principle with a two locus model. We conclude that positive niche construction can both evolve and be maintained when it has other beneficial effects via pleiotropy. This situation may apply generally to the evolutionary maintenance of cooperation.