In this paper, we define a tractable procedure to measure worker incomplete information in the labor market. The procedure, which makes use of earnings distribution skewness, is based on econometric frontier estimation techniques, and is consistent with search theory. We apply the technique to eleven countries over various years, and find that incomplete information leads workers to receive on average about 30-35% less pay than they otherwise would have earned, had they information on what each firm paid. Generally married men and women suffer less from incomplete information than the widowed or divorced; and singles suffer the most. Women suffer more from incomplete information than men. Schooling and labor market experience reduce these losses, but institutions within a country can reduce them, as well. For example, we find that workers in countries that strongly support unemployment insurance (UI) receive wages closer to their potential, so that doubling UI decreases incomplete information and results in 5% higher wages. A more dense population reduces search costs leading to less incomplete information. A more industrial economy disseminates wage information better, so that workers exhibit less incomplete information and higher wages. Finally, we find that foreign worker inflows increase incomplete information, and at the same time reduce average wage levels, at least in the short-run.