This paper examines whether the Action Plan for Promoting Employment and Combating Unemployment, a labor market intermediation program adopted by the Algerian government in 2008, reduced the informality of employment in Algeria. Using repeated cross-section data from the Household Survey on Employment for the period from 1997 to 2013, and a difference-in-difference methodology, we estimate whether the Action Plan has reduced the probability that workers are employed informally in enterprises of more than 5 workers – the type of enterprise that is most likely to be directly affected by the Action Plan. Our results show that the Action Plan has in fact contributed to reducing employment informality in such enterprises, but with heterogeneous effects. More precisely, it reduced informality for employees of establishments of 10 workers or more but had no significant effects on informality for those working in enterprises of 5 to 9 workers. Furthermore, when we restrict our estimates to new entrants only, we do not find statistically significant effects.