The PAR proteins have an essential and conserved function in establishing polarity in many cell types and organisms. However, their key upstream regulators remain to be identified. In C. elegans, regulators of the PAR proteins can be identified by their ability to suppress the lethality of par-2 mutant embryos. Here we show that a nos-3 loss of function mutant suppresses the lethality of par-2 mutants by regulating PAR-6 protein levels. The suppression requires the activity of the sex determination genes fem-1/2/3 and of the cullin cul-2. FEM-1 is a substrate-specific adaptor for a CUL-2-based ubiquitin ligase (CBC(FEM-1)). Interestingly, we find that CUL-2 is required for the regulation of PAR-6 levels and that PAR-6 physically interacts with FEM-1. Our data strongly suggest that PAR-6 levels are regulated by the CBC(FEM-1) ubiquitin ligase thereby uncovering a novel role for the FEM proteins and cullin-dependent degradation in regulating PAR proteins and polarity processes.