Shaw joined the Australian Army in 1964 and he served in the Indonesian-Malaysia confrontation where he spent 18 months with the 4th Battalion, Royal Australian Regiment; stationed just north of Malacca.[2]
Because he was a regular in the Army he was then sent back home to join the 2nd Royal Australian Regiment when Australia became involved in the Vietnam War. In between these two deployments he was given just one week's leave to visit Alice Springs to see his family before travelling to Vietnam on HMAS Sydney. One day, when on patrol in Vietnam, Shaw cut his thumb through to the bone on his machete and was sent back to Australia for, what was ultimately, three operations and multiple skin grafts. Following this injury, and the 6 months spent to recover, Shaw was transferred to the 9th Battalion where he became Section Commander (Corporal) and, later, Acting Platoon Sergeant (Sergeant).[2]
While in the 9th Battalion Shaw met other Aboriginal men from Alice Springs who were serving in Vietnam; including Richard Tilmouth, Charlie Tilmouth, Kenny Laughton, Linton Espey and David Miller and thought it was amazing that six Aboriginal men from Alice Springs (including himself) where serving nearby noting that it was a "fairly big contingent when you work out the percentage of Aboriginal people who went to Vietnam".[2]