The extant species of Nautilus and Allonautilus (Cephalopoda) inhabit fore-reef slope environments across a large geographic area of the tropical western Pacific and eastern Indian Oceans. While many aspects of their biology and behavior are now well-documented, uncertainties concerning their current populations and ecological role in the deeper, fore-reef slope environments remain. Given the historical to current day presence of nautilus fisheries at various locales across the Pacific and Indian Oceans, a comparative assessment of the current state of nautilus populations is critical to determine whether conservation measures are warranted. We used baited remote underwater video systems (BRUVS) to make quantitative photographic records as a means of estimating population abundance of Nautilus sp. at sites in the Philippine Islands, American Samoa, Fiji, and along an approximately 125 km transect on the fore reef slope of the Great Barrier Reef from east of Cairns to east of Lizard Island, Australia. Each site was selected based on its geography, historical abundance, and the presence (Philippines) or absence (other sites) of Nautilus fisheries The results from these observations indicate that there are significantly fewer nautiluses observable with this method in the Philippine Islands site. While there may be multiple possibilities for this difference, the most parsimonious is that the Philippine Islands population has been reduced due to fishing. When compared to historical trap records from the same site the data suggest there have been far more nautiluses at this site in the past. The BRUVS proved to be a valuable tool to measure Nautilus abundance in the deep sea (300–400 m) while reducing our overall footprint on the environment.