Gordon was first assigned to construct fortifications at Milford Haven, Pembrokeshire, Wales. During his time in Milford Haven, Gordon was befriended by a young couple, Francis and Anne Drew, who introduced him to evangelical Protestantism. Gordon was especially impressed with Philippians 1:21 where St. Paul wrote: "For to me, to live is Christ, and to die is gain", a passage he underlined in his Bible and often quoted. He attended diverse congregations, including Roman Catholic, Baptist, Presbyterian, and Methodist. Gordon, who once said to a Roman Catholic priest that "the church is like the British Army, one army but many regiments", never aligned himself with or became a member of any church.