הקהילה היהודית בווינה נוצרה בשלהי המאה ה- 12, והתקיימה עד ל"גזרת וינה" – רדיפות וגירוש בשנת 1420/21. שְלוֹם, בעל מטבעה בחסותו של הדוכס לאופולד החמישי, הנו היהודי הראשון המופיע בכתובים אשר התיישב בווינה. הוא סיפק כסף לייצור מטבעות והיו לו אדמות וכרם בווינה ובסביבה. הוא בנה בית כנסת, בזייטנשטטנגאסה 2 של היום, ונרצח על ידי צלבנים שעברו בווינה בשנת 1196, הוא ו- 15 מבני ביתו.
הקיסר פרידריך השני והדוכס פרידריך השני הוציאו שתי פריבילגיות שהגדירו את מעמדם החוקי של היהודים בווינה ובאוסטריה בשנים 1238 – 1244. הפריבילגיות עוסקות בעיקר בהלוואות ובדמי תיווך.
אחד מגדולי הרבנים בימי הביניים, יצחק בר משה "אור זרוע", חי בווינה בשנות ה- 60 של המאה ה- 13. הרבה מאד יהודים עברו לווינה בשנות ה- 70 וה- 80, בעיקר מבוהמיה וממוראביה. משנת 1340 ואילך היו דוד שטויס ובני משפחתו בעלי עמדה חשובה בקהילה. ה"יודנמייסטר", נציגי הקהילה היהודית ובעלי ידע הלכתי, שירתו בתפקיד רשמי תחת הדוכס והקהילה הייתה כפופה להם. לקהילה היה בית כנסת, כמה מקוואות, בית מרחץ, בית חולים, בית עלמין, וכמה ארגונים דתיים וחברתיים.
בשנות ה- 60 של המאה ה- 14, כשהדוכס רודולף הרביעי נזקק לאשראי גדול יותר, עלה מספר היהודים בווינה. הם באו מהונגריה (אודנבורג, כיום שופרון) ומעיירות קטנות יותר. הקהילה מנתה כ- 900 חברים, שהיוו כ- 5 אחוזים מאוכלוסיית העיר. בשנים 1360 – 1400 הקהילה שיגשגה, ונהייתה למרכז תורני יהודי עם מלומדים מפורסמים כמו אברהם קלאוזנר ומאיר מפולדה.
אך לא לעולם חוסן, והסימן הראשון לכך הייתה השריפה בשנת 1406 , שבעקבותיה נבזזו בתי יהודים על ידי סטודנטים. יותר ויותר נוצרים נכנסו לעסקי ההלוואות, משפחות אצולה נמנעו יותר ויותר מללוות אצל יהודים, והיהודים נהיו פגיעים יותר. טבילה בכפייה והאשמות בתמיכה בהוסיטים הובילו לגירוש יהודי וינה למוראביה (שהייתה פרובינציה של המונרכיה האוסטרית-הונגרית) ולהונגריה, ולרצח ברוטלי של הנותרים בעיר. יהודים רבים מתו בעינויים, אחרים התאבדו על קידוש השם בבתי כנסת כדי לא להיטבל לנצרות, וכ- 200 עד 300 יהודים הועלו על המוקד. המאורעות המכונים "גזרת וינה" ב- 1420/21 הביאו למעשה לחיסולה של קהילה יהודית מאורגנת בווינה למשך מאות שנים, ובמסורת היהודית יצא לה שם רע כמקום מועד לשפיכות דמים.
היהודים גרו בווינה באופן ארעי או קבוע, כשקיבלו פריבילגיות שהתירו זאת. בשנת 1580 בקירוב שוב החל מספרם לעלות בהדרגה, ונוצר צורך לייסד בית עלמין משלהם. בתחילת המאה ה- 17 חיו רוב היהודים באזור שהיום נקרא רופרכטספלאץ. בשנת 1624 נצטוו לעבור לרובע התחתי של וינה , כיום לאופולדשטאט. כדי להגיע לחנויותיהם בפנים העיר היה עליהם לחצות גשר. בעקבות מלחמת שלושים השנים העניק להם הקיסר פריבילגיות שאיפשרו ניידות והבטיחו את יכולתם לספק אשראי לצרכי המלחמה.