The Martian bow shock position is known to be correlated with solar extreme ultraviolet irradiance. Since this parameter is also correlated with the evolution of the solar cycle, it is expected that the Martian bow shock position should also vary over such a period. However, previous reports on this topic have often proved contradictory. Using 13 years of observations of the Martian bow shock by the Mars Express mission over the period 2004 to 2017, we report that the Martian bow shock position does vary over the solar cycle. Over this period, our analysis shows the bow shock position to increase on average by 7% between the solar minimum and maximum phases of solar cycle 23–24, which could be even larger for more extreme previous solar cycles. We show that both annual and solar cycle variations play major roles in the location of the bow shock at Mars.