טאלין נוסדה ככפר אסטוני בשם "לינדניס". העיר מופיעה על המפה של הקרטוגרף הערבי מוחמד אל-אדריסי בשנת 1154 בשם "קאלווני" (Kaleweny), שמקורו במילה "קוליוואן" (ברוסית: Колывань), שהייתה שמה הרוסי של טאלין. העיר שימשה כנקודת חיבור בין רוסיה לסקנדינביה. בשנת 1219 נכבשה העיר על ידי הדנים, אך עוד קודם לכן היו העיר וסביבותיה למטרה למסעי הצלב הצפוניים ותושבי האזור אולצו להתנצר. הדנים מכרו את טאלין וסביבותיה למסדר הטבטוני בשנת 1345. בשנת 1500 הוגבה צריח כנסיית אולף הקדוש שבעיר, והגיע לגובה 159 מטרים. משנת 1549 הייתה הכנסייה הבניין הגבוה בעולם, עד שבשנת 1625 נפגע הצריח ונשרף ממכת ברק. בשנת 1561 נכבשה העיר על ידי השוודים, ובשנת 1721 נכבשה על ידי רוסיה. הצאר פטר הגדול נתן לעיר זכויות עירוניות מצומצמות.

ב-24 בפברואר 1918 הכריז הפרלמנט האסטוני על עצמאות אסטוניה ועל טאלין כעיר בירתה. בנוסף הוקמה ממשלה זמנית. הקיסרות הגרמנית לא הכירה בעצמאותה של אסטוניה וחששה מפגיעה באינטרסים של הגרמנים-הבלטים במדינה. על כן נכבשה טאלין ביום למחרת על ידי הצבא הקיסרי הגרמני. הצבא הגרמני יצא מטאלין בעקבות הסכם הכניעה הגרמני למעצמות ההסכמה ב-11 נובמבר 1918. בעקבות עזיבת הצבא הגרמני ואי ההכרה הסובייטית בעצמאותה של אסטוניה, פתח הצבא האדום בסוף נובמבר במתקפה והתקדם לכיוון טאלין. במתקפתו הגיע הצבא האדום עד כ-34 קילומטרים מזרחית לעיר בסוף דצמבר אותה שנה. במהלך דצמבר הגיעו לטאלין מתנדבים פינים ללחימה בסובייטים. בעקבות התקפת הנגד האסטונית בתחילת ינואר 1919 התרחק קו החזית מזרחה. בתחילת ינואר 1920 נכנסה הפסקת אש לתוקף וחוזה השלום עם רוסיה הסובייטית נחתם ב-2 בפברואר אותה שנה. ב-2009 הוקם בטאלין עמוד הניצחון לזכר מלחמה זו ובראשו צלב החופש שחולק למצטיינים בה. לאחר השתלטות הסובייטים ב-1940 הייתה לבירת הרפובליקה הסובייטית של אסטוניה, שסופחה במהרה לברית המועצות. ב-1941 נכבשה על ידי הנאצים, וב-1944 נתפסה שוב על ידי הסובייטים.

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

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