Media trust and political trust are both very important to the stability of democratic political systems. However, research on the relationship between media trust and political trust is rare. This study tries to examine the relationship between media credibility and political trust from 2003 to 2018 using a longitudinal approach. Media credibility was measured by asking respondents to score from 0 points (least credible) to 100 points (most credible) the overall news coverage from newspapers, magazines, radio stations, TV channels, and Internet sites. Political trust was measured by asking respondents to indicate the extent to which they agreed with two statements using a 5-point Likert-type scale: "The government seeks to create maximum welfare for the people" and "What government officials say in the media is believable." The two scores were then averaged to create the measure of political trust. Analyzing survey data collected by the "Taiwan Social Change Survey" and the "Taiwan Communication Survey," we found that respondents evaluated low levels of both media credibility and political trust, with levels declining year by year. The results show the positive relationship between TV credibility and political trust, a finding that fits the "virtuous circle theory." Data also show a negative relationship between radio credibility and political trust, which fits the "media malaise theory."