We investigate differences in quit, layoff and hiring rates in high versus low minimum wage regimes using Canadian data spanning 1979 to 2008. The data include consistent questions on job tenure and reason for job separation for the whole period. Over the same time frame, there were over 140 minimum wage changes in Canada. We find that higher minimum wages are associated with lower hiring rates but also with lower job separation rates. Importantly, the reduced separation rates are due mainly to reductions in layoffs, occur in the first 6 months of a job, and are present for unskilled workers of all ages. Our estimates imply that a 10% increase in the minimum wage generates a 3.9% reduction in the layoff rate. We present a search and matching model that fits with these patterns and test its implications. Overall, our results imply that jobs in higher minimum wage regimes are more stable but harder to get.