In Australia, inspections of food premises are routinely conducted by environmental health officers (EHOs) using a checklist approach; the checklist is either manually written or stored into an electronic device. EHOs primarily assess cleanliness by visual inspection. Microbiological sampling is limited to those occasions requiring statutory evidence collection. The evidence gap between visual inspection and microbial sampling might be assisted by using commercially available rapid adenosine triphosphate (ATP) testing devices. This article presents a pilot study using ATP testing together with a new sampling algorithm in the assessment of surface cleanliness. Surfaces and implements were tested in eight food premises using ATP testing to determine cleanliness on items that passed the visual test of cleanliness. Cleanliness was verified using a cleaning intervention step. Of the 49 of 72 (68%) surfaces and implements assessed as visually clean, they were shown to have inadequate cleanliness (p = .001). The findings support using ATP testing with the new algorithm, as this could provide a reliable approach for surveillance of surface cleanliness by EHOs.