Tribal villages in Nepal’s “Middle Hills” region practice traditional farming techniques that contribute to ongoing decreases in agricultural productivity. The introduction of conservation agriculture practices, such as strip tillage and intercropping with nitrogen-fixing legumes can increase long-term farm profitability and help ensure long-term soil productivity. In this study, survey and trial plot data from three tribal villages is used to provide an analysis of profitability and changes in labor requirements associated with the introduction of strip tillage, intercropping and residue management. The current farmer practice of millet monocropping (T1) was least profitable of all systems and cowpea monocropping (T2) was the most profitable. Cowpea monocropping also required the least labor and thus, is the most suitable candidate for adoption at the time of this study. However, millet and cowpea intercropping with a minimum (strip) tillage regime (T4) may provide higher profits than all other treatments once the long-term benefits of strip-tillage take effect. In addition, labor requirements for T4 are most in line with current labor division by gender and as a result, this treatment might prove the most suitable for adoption over the long term. It is recommended that high quality legume seed be provided to improve smallholder livelihoods and increase regional food production.