Maya began working as a trial lawyer in the city of Valledupar where he became sectional manager of the Social Security Institute.

He was also an auxiliary magistrate of the Labor Cassation Chamber of the Colombian Supreme Court of Justice.

Maya's appointment ceremony took place in the Casa de Nariño Presidential Palace.

In 2006 and 2007 Maya was questioned by the Colombian media, opposition politicians and others for the involvement of some members of his stepfamily in a parapolitics scandal.

His nephew in law and former Senator of Colombia Álvaro Araújo Castro and his father Álvaro Araújo Noguera (Maya's brother in law) were also questioned and indicted in parapolitics related activities.