לפי ממצאים ארכאולוגיים, סארמאה היה מיושב לפחות מהאלף השלישי לפנה"ס. בסאגות סקנדינביות עתיקות, סארמאה מוזכר תחת השם "אֵיְסִיסְלָה", שפירושו כמו באסטונית: "אי המחוז". זהו מקור השם הגרמני והשוודי של האי: אֶסֵל (Ösel), או בלטינית אוֹסִילִיה (Osilia). בסאגות מדובר על מקרי טבח רבים בין הויקינגים לבין תושבי האיים. סארמאה היה המחוז העשיר ביותר באסטוניה העתיקה וארץ מוצאם של הרבה שודדי-ים אסטונים, לפעמים ידועים בשם "הוויקינגים המזרחיים". בכתבי-יד מלטביה מסופר על התארגנות של שש־עשרה ספינות ו-500 אנשי סארמאה שבזזו ערי־חוף בדרום שוודיה, אזור שבעבר היה שייך לדנמרק.

בשנת 1227 סארמאה נכבשה בידי המסדר הליבוני, אבל הפכה למוקד מרד אסטוני. כשהמסדר הובס בידי הצבא הליטאי בשנת 1236, תושבי האי סארמאה מרדו.

בשנת 1560 נמכר האי לדנמרק, אך כעבור 85 שנה השליטה באי ניתנה לשוודיה.

בשנת 1721 עברה השליטה בסארמאה לאימפריה הרוסית ביחד עם שאר אסטוניה השוודית, בהתאם להסכם ניסטאד. האי המשיך להיות תחת שליטה רוסית עד שנכבש על ידי גרמניה באוקטובר 1917. לאחר מלחמת העולם הראשונה קיבלה אסטוניה עצמאות והאי סארמאה היה לחלק מאסטוניה. ב-1940 סופחה אסטוניה ביחד עם האי סארמאה לברית המועצות כרפובליקה סובייטית. האי נכבש באופן זמני בידי גרמניה במלחמת העולם השנייה.

כאשר קיבלה אסטוניה עצמאות ב-20 באוגוסט 1991, צורף סארמאה לרפובליקה כמחוז סארה.