הקשר הראשון הידוע בין איסלנד לפולין החל בשנת 1613 כאשר הנזיר הצ'כי דניאל סטרייץ-וטרוס ביקר באיסלנד. בשנת 1638 הוא הוציא ספר בפולנית על מסעותיו באי בשם "Islandia, álbo Krotkie opisanie Wyspy Islandiy" (פורסם בלשנו שבפולין)[1]. במאה ה-19 הגיע הסופר הפולני אדמונד חויצקי לאיסלנד כמזכיר הקיסר הצרפתי העתידי נפוליאון השלישי.[2] בשנת 1857 פרסם חויצקי ספר בצרפתית בשם "Voyage dans les mers du nord à bord de la corvette la Reine Hortense" המתאר את מסעותיו וניסיונו באיסלנד.[3]
ביולי 1945, לפני סיומה הרשמי של מלחמת העולם השנייה, איסלנד הכירה בממשלת האחדות הלאומית הפולנית.[4] היחסים הדיפלומטיים בין שתי המדינות החלו רשמית בינואר 1946.[4] בשנת 1956 פתחה פולין קונסוליה ברייקיאוויק שנשארה פתוחה עד 1981.[5] בשנת 2008 פתחה פולין מחדש את הקונסוליה הכללית ברייקיאוויק. מאוחר יותר שודרגה הקונסוליה הפולנית לשגרירות.[5]
בשנות ה-60 החלו מהגרים פולנים להגיע לאיסלנד על מנת לעבוד במספנות ברחבי האי. בשנות ה-80 איסלנד הייתה זקוקה לכוח עבודה, ולכן החלה לגייס עובדים פולנים.[5] באמצע שנות האלפיים מנתה הקהילה הפולנית יותר מ-20,000 איש.[9] לאחר המשבר הפיננסי בשנת 2008 הקהילה הפולנית ירדה בחצי, אך כיום (2021) הפולנים הם האוכלוסייה הזרה הגדולה ביותר באיסלנד, והם מהווים 3% מהתושבים.[5]
