It helps to look at the German voting system by considering German history rather than comparing it directly to other modern systems like the English first past the post.
In the second empire of 1871, elections to the Reichstag indeed followed the majority vote system; however, a candidate required a 50 % share of the votes to be elected and if nobody reached that in the first round a runoff was held. Throughout the second empire, there were calls to introduce a proportional vote but that was never implemented.
In the Weimar Republic from 1919, a proportional vote was instead introduced. In the interest of brevity I will merely describe it as follows: the number of votes a party achieved divided by 60,000 and rounded according to standard rules pretty much equalled the number of seats the party would get. (There were restrictions that resulted in the USPD not gaining a single seat from its 235,145 votes in 1924 but these would be too much for this question.)
After the war, the constitutional convent of the western occupied zones decided to, in principle, stick to proportional representation but with a fixed-size parliament rather than a varying-size one as in the Weimar era. Thus, in principle only the national vote share determines how many seats of the currently 598 a party receives. To ensure regional representation and distribution across the states (federalism), the national vote share is broken down to a state vote share and the seats are actually filled on a state level.
However, representation at state level does not ensure representation of all parts of the country in parliament—a feature automatically implemented in the British system where each MP directly represents exactly one certain bit of land, all of which together add up to the UK (ignoring Sinn Fein and the likes). Thus, it was decided to make a certain part of the seats directly elected ones with voting districts. While voting districts are still much larger than their UK counterparts (but smaller than their US counterparts) each part of the country has exactly one locally elected MdB (Mitglied des Bundestages, member of the Bundestag) that e.g. local businesses or citizens can address with any issues they have.
Thus, in a nutshell the full chain of thoughts is:
- 598 seats in parliament for proportional representation
- 299 of which are designated for regional representation in a first past the post system.
It might be worth mentioning that the overhang seats in the current system only exist because a strictly proportional representation (as is desired) cannot be achieved with directly elected candidates only. There will always have to be some seats filled by some other mechanism. How to achieve this is a political discussion, the current system is Germany’s current answer.