There have been significant improvements in traditional trade policies in the past few decades. However, these improvements can only be fully effective when they are complemented with a favorable investment climate. This study focuses on a particular aspect of investment climate, namely labor regulations, and shows how these regulations can be discouraging from exporting. Using firm level data from 26 countries in Eastern Europe and Central Asia region, the paper empirically shows that firms that cannot create new jobs due to stringent labor regulations are less likely to export. Firms that plan to export expand their sizes before they start to export. However the rigidities in labor markets make this adjustment process costly. Higher costs of employment decrease operating profits and lead to a higher productivity threshold level required for entering export markets. As a result, a smaller fraction of firms can afford to export.