Believability is an important characteristic of intelligent virtual agents, however, very few attempts have been made to define and formalise it. This paper provides a formal analysis of believability, focused on diverse aspects of believability of the agents and the virtual environment they populate, approaching the problem from the perspective of the relationship between the agents and the environment. The paper also presents a computational believability framework built around this formalism, featuring virtual agents able to reason about their environment – the virtual world in which they are embedded, interpret the interaction capabilities of other participants, own goals and the current state of the environment, as well as to include these elements back into interactions. As a proof of concept we have developed a case study, a prototype of an ancient Sumerian city (Uruk), where believable virtual agents simulate the daily life of its citizens.