This paper deals with the analysis of conditions that influence the employability of graduates of HEIs under state’s control in the State of Mexico. A systemic approach was used to conduct this piece of research based on an exploratory study that included the organization of workshops with employers, interviews with HEI’s authorities and a survey applied to graduates. All these tools were used to identify the main variables that are influential for the employability of graduates of the HEIs under state control of the four regions of the state: South, East, Valley of Mexico and Valley of Toluca. Results show that there is a serious lack of coordination among the actors involved in job generation and those dedicated to educating professionals. A lack of soft skills in graduates was identified as a limiting factor for them to get good jobs, along with a very unstable socioeconomic environment. These factors interact to define a complicated situation for employability in the four regions of the state.