Taking advantage of a recent relaxation of Japanese government's data release policy, we conduct a cross-national analysis of micro data from Japan's Employment Status Survey and its U.S. counterpart, Current Population Survey. Our focus is to document and contrast changes in long-term employment and job security over the last twenty five years between the two largest advanced economies. We find that in spite of the prolonged economic stagnation, the ten-year job retention rates of core employees (employees of prime age of 30-44 who have already accumulated at least five years of tenure) in Japan were remarkably stable at around 70 percent over the last twenty-five years, and there is little evidence that Japan's Great Recession of the 1990s had a deleterious effect on job stability of such employees. In contrast, notwithstanding its longest economic expansion in history, the comparable job retention rates for core employees in the U.S. actually fell from over 50 percent to below 40 percent over the same time period. The probit estimates of job loss models in the two nations also point to the extraordinary resilience of job security of core employees in Japan, whereas showing a significant loss of job security for similar employees in the U.S. Though core employees in Japan turned out to have weathered their Great Recession well, we find that mid-career hires and young new job market entrants were less fortunate, with their employment stability deteriorating significantly. We interpret the findings, based on the theory of institutional complementarity, and derive lessons for policy makers around the world who are currently facing their own Great Recessions and developing effective policy responses.