Waters undertook his basic flight instruction at No. 1 Elementary Flying Training School in Narrandera, New South Wales, where he flew De Havilland Tiger Moths. He completed his training on CAC Wirraways and received his wings as a sergeant pilot at No. 5 Service Flying Training School in Uranquinty. Posted to No. 2 Operational Training Unit at Mildura, Victoria, he converted to P-40 Kittyhawk fighters. Once, while he was on leave, Waters was reportedly gaoled in Moree, New South Wales, for not carrying an identity card, which was one of the racially discriminatory institutions affecting Aboriginal people at the time. On 14 November 1944, he was posted to No. 78 Squadron, a fighter unit based on the island of Noemfoor, off Dutch New Guinea. When he arrived, he was allocated a P-40 Kittyhawk. By chance, a previous pilot had nicknamed the plane "Black Magic" and painted those words on its nose. Waters found the name of his plane an amusing coincidence and chose to retain it.

By this stage of the war, Japanese aircraft were almost non-existent in the South West Pacific theatre; No. 78 Squadron's main role was ground attack, bombing and strafing enemy positions. Waters flew 95 sorties from Noemfoor, and later from the air bases at Morotai and Tarakan, in Borneo. During one mission, his aircraft was struck by a 37 mm cannon shell that embedded itself behind him in the cockpit without detonating. He flew for another two hours, with the possibility of the shell exploding at any time, a situation he likened to having a loaded gun against his head. "I'll tell you what", he said after returning to base, "that was the best landing I ever made". On 1 January 1945, he was promoted to flight sergeant. By the end of the war, Waters was commanding operations whose personnel included commissioned officers. A colleague described him as a "gaunt, genial figure, humble despite his daring feats". As well as flying, Waters held the RAAF middleweight boxing title