Iodine is naturally found in sea water and soil but it is not evenly distributed, with many areas in the world with low levels of iodine. Iodine accumulates naturally in fish, and plants growing in iodine-rich soil. Mammals that eat these plants get iodine from them, which then accumulates in the milk, making dairy and its products (e.g. cheese) another natural source of iodine. Table 1 from the Iodine deficiency section at the American Thyroid Association web page contains a brief list of iodine-rich food.
Quoting the web site:
What are the sources of iodine?
Iodine is present naturally in soil and seawater. The availability of iodine in foods differs in various regions of the world. Individuals in the United States can maintain adequate iodine in their diet by using iodized table salt (unless they have to restrict the amount of salt in their diet), by eating foods high in iodine, particularly dairy products, seafood, meat, some breads, and eggs, and by taking a multivitamin containing iodine (see below). However, the amount of iodine in foods is not listed on food packaging in the U.S., and it can be difficult to identify sources of iodine in foods.
As mentioned, the amount of iodine in some food depends on how much iodine is present in the water or soil. For example, in the International Council for the Control of Iodine Deficiency Disorders (ICCIDD) there is some mention about the natural sources of iodine and its limitations:
Most of the iodine we consume comes from what we eat and drink. Seafood is usually a good source because the ocean contains considerable iodine. Freshwater fish reflect the iodine content of the water where they swim, which may be deficient. Other foods vary tremendously in iodine content, depending on their source and what may have been added. Plants grown in iodine-deficient soil do not have much iodine, nor do meat or other products from animals fed on iodine-deficient plants. Because the breast concentrates iodine, dairy products are usually a good source, but only if the cows get enough iodine.
Iodine deficiency causes important health problems. Iodine is necessary to produce thyroid hormones. Lack of thyroid hormones causes hypothyroidism, cretinism and goiter. However, iodine deficiency is not mortal per se.
Conclusion
As a consequence, in the Middle Ages iodine deficiency was not an issue in places where water and/or soil was rich in iodine. In other places they would suffer of iodine deficiency, leading to a higher impact of the related diseases.
Nowadays, iodine is added artificially to food in order to prevent iodine deficiency. This practice has diminished the impact of iodine deficiency-related diseases. However, iodine deficiency is still an important issue today, as reported by the World Health Organization in its map describing the Degree of Public Health Significance of Iodine Nutrition. As shown in the map, in many places in the world there is still risk of severe iodine deficiency.

Sources:
- Iodine deficiency - Wikipedia
- American Thyroid Association
- World Health Organization
- International Council for the Control of Iodine Deficiency Disorders (ICCIDD)