The use of unmanned aerial vehicles with multiple onboard sensors has grown significantly in tasks involving terrain coverage such as environmental and civil monitoring, disaster management, and forest fire fighting. Many of these tasks require a quick and early response, which makes maximizing the land covered from the flight path a challenging objective, especially when the area to be monitored is irregular, large and includes many blind spots. Accordingly, state-of-the-art total viewshed algorithms can be of great help to analyze large areas and find new paths providing maximum visibility. This article shows how the total viewshed computation is a valuable tool for generating paths that provide maximum visibility during a flight. We introduce a new heuristic called visibility-based path planning (VPP) that offers a different solution to the path planning problem. VPP identifies the hidden areas of the target territory to generate a path that provides the highest visual coverage. Simulation results show that VPP can cover up to 98.7% of the Montes de Malaga Natural Park and 94.5% of the Sierra de las Nieves National Park, both located within the province of Malaga (Spain) and chosen as regions of interest. In addition, a real flight test confirmed the high visibility achieved using VPP. Our methodology and analysis can be easily applied to enhance monitoring in other large outdoor areas.