Background: India is home to the largest number of underweight and stunted children in the world, but its national Integrated Child Development Services (ICDS) programme has had negligible impact on the nutritional status of young infants. Aim: To use two innovative approaches – the Optifood tool and mobile phones – to strengthen counselling components of the ICDS programme to improve complementary feeding (CF) practices of 9-11 month old infants, in a rural district in Haryana state, Northern India. Methods: Optifood, a novel tool using linear programming analyses to formulate and evaluate food-based recommendations (FBRs), was used to strengthen existing ICDS FBRs. These FBRs were tested with mothers of young infants in a week-long trial, and promoted in a 6-week pilot test of a mobile phone-delivered (mHealth) intervention with 12 health workers and 60 mothers of 9-11 month old infants, using a before and after comparison. Evaluation of outcomes was based on Optifood analyses, 24-hour dietary recalls, food frequency questionnaires, open-ended structured questionnaires, an intervention development workshop, focus group discussions, and in-depth interviews. Results: Local food-based approaches are unable to meet recommended nutrient intakes (RNIs) for seven key nutrients. However, FBRs alone could ensure dietary adequacy (i.e. ≥65% Recommended Nutrient Intake) for at least six nutrients for most infants. In the trial to test FBRs, the proportion of mothers feeding their infants legumes, vegetables and fruit at endline was significantly greater (p<0.05) than at baseline; no significant increases in the proportion of mothers feeding their infants grains, dairy, fats or egg were reported. Mothers reported 19 barriers to following the promoted FBRs, which were used to develop motivating statements for their promotion in a mHealth intervention. The mHealth pilot test findings suggest that the intervention was convenient, feasible and acceptable. Based on self-report, health workers adhered to the planned contact of 20 mobile phone calls during the study period. Compared to baseline, there were significant increases (p<0.05) in the following at endline: (i) infants’ median servings per week of grains, legumes, fruit, and added fats; (ii) proportion of mothers reporting feeding eggs, undiluted milk and green leafy vegetables; (iii) proportion of infants meeting promoted FBRs for all foods except dairy; and (iv) maternal knowledge regarding food consistency. Conclusions: This is the first study to use linear programming analyses to strengthen existing governmental FBRs, and to use mobile phones for CF counselling. Findings suggest that additional, complementary intervention(s) are required to improve the micronutrient status of infants. While evidence from a randomised controlled trial is needed, study findings provide valuable insights into the utility of evidence-based FBRs and mobile phones to enhance the impact of ICDS and CF programming and research strategies in the study setting, and potentially globally.