Polynucleotides, polypeptides, plant cells expressing same and methods of using same for increasing abiotic stress tolerance water use efficiency (WUE), fertilizer use efficiency (FUE), biomass, vigor and/or yield of a plant. The method is effected by expressing within the plant an exogenous polynucleotide encoding a polypeptide comprising an amino acid sequence at least 80% homologous to the amino acid sequence selected from the group consisting of SEQ ID NOs:33, 34, 30, 27-29, 31, 32, 35-52, 1401-1403, 1405-1435, 1437-1494, 1496-1542, 1544-1553, 1555-1559, 1561-1827, 1829-1866, 1868-2450, 2453-2458, 2460-2463, 2465-2481, 2483, 2485-2746, 2765-2769, 3052-3065 and 3067-3259, thereby increasing the water use efficiency (WUE), the fertilizer use efficiency (FUE), the biomass, the vigor and/or the yield of the plant.