[3][4] Valencia was already familiar with the politics of Colombia in the 1950s; her father, Guillermo Valencia had been an active member of the Colombian Conservative Party, a Congressman, Minister of Finance, Governor, and presidential candidate in the elections of 1918, and 1930, and her brother Guillermo León had been Councilman, Congressman, Minister of Foreign Affairs, and Ambassador.

Valencia seized the opportunity and joined the National Popular Alliance, a political movement started by General Rojas.

Her direct lobbying to the President paid off, On 28 July 1954 in an unusual move, General Rojas who had maintained the National Constituent Assembly that had been started by his predecessor, the deposed Roberto Urdaneta Arbeláez, named Valencia Member of the National Assembly in representation of the Conservative Party with Teresa Santamaría Santamaría as her alternate, thus becoming the first woman to serve in a Colombian national legislative body; she was later joined by Esmeralda Arboleda Cadavid in representation of the Liberal Party with María Currea Manrique as her alternate.

They joined forces and introduced the Legislative Act on the Citizenship of Women to be studied and debated by the Assembly.

On 21 September 1955, General Rojas Pinilla appointed Valencia governor of her native Department of Cauca,[6] the first woman to ever exercise an executive position in the country, a post in which she served until September 16, 1956, when she was called to Bogotá to serve as the first female government minister, in the Ministry of National Education.