For Marine Protected Areas (MPAs) to be effective in conservation their zoning and management needs to be based on scientific data. Obtaining information on spatio-temporal occurrence patterns of cetaceans can be especially challenging. This study used platforms of opportunity (i.e., fishing monitoring vessels) from May 2004 to May 2012 as a cost-effective way to address this knowledge gap in the Wakatobi National Park (WNP) at the heart of Coral Triangle, an important area for cetaceans in Indonesia. A database was created of cetacean sightings per surveyed days at sea, allowing for an analysis of species diversity and habitat use around the islands. Of the 11 cetacean species identified, spinner and bottlenose dolphins were sighted most often, followed by melon-headed and sperm whales. Spinner dolphin showed a wide distribution in the area, whilst bottlenose dolphin and melon-headed whale occupied the waters between the main islands and south atolls. Sperm whales occurred mostly in waters north of the main islands and as melon-headed whales, mostly in deep waters. Most cetacean sightings occurred in the zones designated for human use, indicating where potential conflicts might occur. No sightings were found in the Park core zone, suggesting a mismatch between WNP design and the cetacean ecological needs. Based on a sub-sample of the dedicated fishing monitoring sightings a sighting frequency was derived. Small and large cetaceans were reported mostly during inter-monsoonal seasons, possibly related to increased prey availability due to seasonal upwelling and increased survey activity. Inter-annual occurrence of cetaceans was variable, with no large cetaceans being sighted in 2010–2012, likely due to reduced survey efforts. In areas with limited resources for designated surveys, the use of platforms of opportunity can be a cost-effective tool to provide valuable data on cetacean occurrence. While data collection protocols in the WNP can be improved further, the results presented here already help identify potentially important areas as well as highlight where to direct designated research efforts. We advise to protect currently unprotected cetacean important habitats, and strictly regulate human activities in the current use zones for future WNP rezoning processes.