Searching for jobs is challenging, and online platforms now often offer tailored job recommendations. In a randomized controlled trial with over 1,250 participants, we evaluate recommendations based on prior experience and based on skill profiles assessed at study enrolment, respectively. We find that on average both types of recommendations improve job finding rates. Profile-based recommendations are especially effective for individuals with limited experience and mismatch in the prior job, while experience-based recommendations may slower job finding for those with limited experience but a well-matched previous job. These findings highlight the need to align job search advice with jobseekers' skills.