We consider the problem of performing condition-based maintenance on a set of geographically distributed assets via a single maintenance resource that travels between the assets’ locations. That is, we dynamically determine the optimal positioning of the maintenance resource and the optimal timing of condition-based maintenance interventions that the maintenance resource performs. These decisions are made as a function of the conditions of the assets and the current location of the maintenance resource to minimize total expected costs, which include downtime, travel, and maintenance expenses. This holistic approach enables us to study unique trade-offs, namely, maintaining an asset early if the maintenance resource is currently close by, or alternatively, optimally repositioning the maintenance resource or having it idle in key locations in anticipation of asset deterioration. We model the location of the maintenance resource and assets using a graph representation and the assets’ deterioration process as a discrete-time Markov chain. We formulate a Markov decision process to obtain the optimal policy for the maintenance resource (i.e., where to travel, idle, or repair). We explore the properties of the optimal policies (analytically and numerically) and how they are affected by the graph structure. Finally, we develop and analyze some implementation-friendly heuristic policies.