Abstract This study was performed to evaluate the ability of cellulolytic fungi and wheat straw incorporation to improve the nodulation, growth and nitrogen status of fenugreek grown in saline soils. NaCl addition to the growth medium at rates of 0.5 and 1% strongly decreased the enzymatic activity of the ten tested moulds. Three of these fungi, Aspergillus niger, Chaetomium globosum and Trichoderma harzianum, showed the highest enzymatic activity. The three moulds have the ability to degrade straw in the presence of NaCl and T. harzianum was the best straw degrader. Inoculating the plants with Rhizobium meliloti strain TAL 1373 and cellulolytic fungi slightly promoted nodulation, growth and nitrogen accumulation when plants were grown with the addition of 0.5% NaCl when compared to plants inoculated with R. meliloti alone. However, application of wheat straw with cellulolytic fungi significantly enhanced growth, nodulation and nodule efficiency at 0.5 and 1.0% salinity. The greatest values of nodulation and growth parameters were obtained with a straw-Trichoderma harzianum combination. Cellulolytic fungi and wheat straw increased the concentration of Ca, Mg and K in the shoots and roots of plants. The increase in dry matter production and N content was mainly due to improved N2 fixation reflected by enhanced formation and growth of nodules as well as nitrogenase activity.