Voting Advice Applications (VAAs) are online decision support systems that try to match voters with political parties or candidates in elections, typically based on how each responds to a number of policy issue statements. Such VAAs play a major role in many countries. In this paper, we describe the development and large-scale application of a new innovative matching algorithm for the most widely used VAA in Finland. We worked closely with the owner of the VAA, the largest daily newspaper in Finland, Helsingin Sanomat. Their previous algorithm, which one might call a “naive” approach, was improved by including measures of candidate’s political power and influence, using proxy variables of media visibility and incumbency status. The VAA was implemented for the 2015 Parliamentary Election in Finland; our matching algorithm was used by 140,000 voters (26.7% of the electorate) in the Helsinki election district. The innovative algorithm generated recommendations that many voters were happy about, followed by users’ incidental comments that this was the first time the VAA recommended candidates they wanted to vote for. This showed the importance of catering to different kinds of voters with a model not previously considered by any VAA in any country.