Recommender Systems use implicit and explicit user feedback to recommend desired products or items online. When the recommendation item is a task or behavior change activity, several variables, such as the difficulty of the task and users’ ability to achieve it, in addition to user preferences and needs, determine the suitability of the recommendations. This paper focuses on how user ability and task difficulty concepts can be integrated into the recommendation process to personalize health activity recommendations. To this end, we compare five approaches, some borrowed from the sports and gaming world, and explore their application, advantages, and drawbacks. Through a study of two weeks, we obtained a suitable dataset to investigate how these algorithms can be used for a health recommender system (HRS) and which one is the most appropriate choice for an online HRS in terms of characteristics and flexibility required for behavior change related tailoring. We compared this choice with a baseline algorithm as part of a fully functional HRS to assess the feasibility and impact of integrating the user ability and required effort concepts on the user engagement with the recommendations in an online longitudinal study of two weeks. The results overall suggest that such integration is effective, and in addition to realizing health behavior change requirements, it improves user engagement with the recommendations.