Veliotes joined the U.S. Foreign Service in 1955. He served as consular officer in Naples in 1955-57 and economic officer in Rome in 1957-60 before returning to the U.S. to work in the Secretariat and then in the Bureau of Cultural and Educational Affairs from 1962 to 1964. He then served as political officer New Delhi (1964–66) and Vientiane (1966–69) before being selected as a Woodrow Wilson Fellow at Princeton University in 1969.
Veliotes was Special Assistant to the Deputy Secretary of State (1970–73), then served as Deputy Chief of Mission in Tel Aviv, returning to the Department of State as Deputy Director of the Policy Planning Staff (1976–77) and then Deputy Assistant Secretary of State for Near Eastern and South Asian Affairs (1977–78). He was Ambassador to Jordan (1978–81) and Assistant Secretary of State for Near Eastern and South Asian Affairs (1981–84). He then served as Ambassador to Egypt until his retirement from the Foreign Service in April, 1986.[3][4]