ב-1972, לאחר מספר שנים בהן הופיעה הלהקה במועדונים ובמכללות באזור לונדון, קיבלה קווין הזדמנות להקליט קלטת ניסיונית של מספר שירים באולפני "De Lane Lea", במטרה לנסות את הציוד החדש במקום. הקלטת כללה חמישה שירים: "Keep Yourself Alive", "The Night Comes Down", "Great King Rat","Jesus" ו-"Liar". לאחר ניסיונות רבים למצוא חברת הפקות, הסכימו אולפני "Trident" בבעלות האחים נורמן וברי שפילד, להקליט באולפנם כשהתנאי היה שהלהקה תוכל להקליט ללא תשלום אך ורק מחוץ לשעות העבודה באולפן שהיו בדרך כלל בשעות הלילה המאוחרות ועד הבוקר. בתנאים אלה ובעבודה דחוקה בת מספר חודשים, מיוני עד נובמבר, הקליטה הלהקה את אלבום הבכורה "Queen" (קווין).
האלבום, שהושפע מסגנונות הרוק הכבד והרוק המתקדם, יצא לחנויות שמונה חודשים לאחר סיום ההפקה, ביוני 1973, מאחר שאף חברת תקליטים לא הסכימה להחתים את הלהקה חסרת הניסיון. כשלבסוף הוציאו אולפני "Trident" את האלבום תחת שמם ובהפצת חברת התקליטים "EMI". האלבום הגיע למקום ה-24 במצעד הבריטי ואף זכה לביקורות טובות כאשר מבקר מגזין הרולינג סטון, גורדון פלטצ'ר, כתב: ""אלבום הבכורה שלהם, Queen, הוא נפלא". האלבום לא זכה להצלחה רבה או היווה פריצת דרך בשביל הלהקה וכן גם הסינגל שיצא מהאלבום, "Keep Yourself Alive", זכה להתעניינות דלה. על אף זאת, הלהקה המשיכה בהופעותיה ובאותה שנה יצאה לסיבוב ההופעות העולמי הראשון שלה.
שנה לאחר מכן, במרץ 1974, הוציאה הלהקה את אלבומה השני, "Queen II". האלבום הגיע למקום החמישי במצעדים הבריטיים, והסינגל שנכתב בידי פרדי מרקיורי, "Seven Seas Of Rhye", הגיע למקום העשירי והפך ללהיט הראשון של הלהקה. האלבום עצמו היווה סוג של אלבום קונספט אפל, עם קטעים אינסטרומנטליים ארוכים, שימוש ברבדים מוזיקליים רבים וכן גם שאב השראה ממיתולוגיה ואגדות. לאחר יציאת האלבום יצאה הלהקה לסיבוב הופעות נוסף, הפעם בבריטניה ובארצות הברית, לצד הלהקה מוט דה הופל. בסיבוב הופעות זה זכתה הלהקה להכרת הציבור בשל הופעותיה הווירטואוזיות והאנרגטיות, אך במהלכו חלה מיי בצהבת והסיבוב הופסק באמצעו. בנוסף לכך, מכירות האלבום בארצות הברית היו חלשות במיוחד, בדומה לקודמו.
באותה שנה החלה הלהקה לעבוד על אלבומה השלישי, כאשר מיי הצטרף אליהם בהמשך בעקבות שיפור במצבו הבריאותי. לקראת סוף השנה הוציאה הלהקה את האלבום "Sheer Heart Attack". בניגוד לקודמיו, האלבום זכה להצלחה אדירה והגיע לראש המצעדים בבריטניה, נמכר היטב באירופה והגיע למעמד של "אלבום זהב" בארצות הברית. האלבום כלל שילוב של סגנונות מוזיקליים שונים, כמו תזמורות, רוק כבד, בלדות, וודוויל ורגטיים. באלבום זה החלה הלהקה להתרחק מהסגנון של אלבומי קונספט ונושאים מיתולוגיים כמו בשני האלבומים הקודמים, ופנתה לכיוון של שירים המתאימים יותר לרדיו. הסינגל שיצא מהאלבום, "Killer Queen", הגיע למקום השני במצעדים בבריטניה והפך ללהיט הראשון של הלהקה בארצות הברית, כאשר הגיע למקום ה-12 במצעדי הבילבורד. הסינגל השני שיצא מהאלבום, "Now I'm Here", הגיע למקום ה-11 במצעדים בבריטניה.
לקראת סוף השנה, הלהקה יצאה למסע ההופעות העולמי הראשון שלה כלהקה עצמאית, כאשר כל אחד מחברי הלהקה מצויד במגוון תלבושות ססגוניות שעוצבו על ידי המעצבת זנדרה רודז. בהופעות נעשה שימוש רב בסטים של תאורה מסיבית ואפקטים ויזואליים מרהיבים. הלהקה הופיעה בארצות הברית וכן בפעם הראשונה בקנדה. בסיבוב הופעות זה הביקוש לכרטיסים היה עצום והלהקה הוסיפה הופעות לא מתוכננות רבות. העומס שנוצר הוביל לדלקות גרון שפקדו את מרקיורי תכופות. הסיבוב כלל לראשונה גם הופעות ביפן, שם הגיע האלבום השלישי למקום הראשון במצעדים.
באותה תקופה, האמרגן של הלהקה, ג'ים ביץ', ניהל משא ומתן עם הבעלים של אולפני "Trident", האחים שפילד, במטרה להוציא את הלהקה מהחוזה שחתמו עם החברה. חברי הלהקה רצו להשתחרר מהחוזה לאור העובדה שבמהלך ארבע השנים בהן היו חתומים תחת החברה הם כמעט ולא הרוויחו כסף. כתוצאה מכך נותרו חברי הלהקה ללא אמרגן. ההצעה הראשונה שקיבלו היה פיטר גרנט, האמרגן של לד זפלין, שרצה להחתים אותם יחד עם לד זפלין בחברת התקליטים החדשה שלהם "Swan Songs". ההצעה לא התאימה לקווין וחברי הלהקה החליטו לשכור את האמרגן של אלטון ג'ון, ג'ון ריד.
ההצלחה הבינלאומית (1975–1979).
בשנת 1975, לאחר הפרידה מהנהלתם של אולפני "Trident", הלהקה זכתה לתקציב גדול יותר, וכך הקליטה שיר פרי עטו של מרקיורי במשך שלושה שבועות. השיר, "Bohemian Rhapsody", שילב בלדת רוק ביחד עם קטע אופראי ונמשך כמעט שש דקות. אף על פי שרבים המליצו ללהקה לא לפרסם את השיר בטענה שמדובר בכישלון חרוץ, שלח מרקיורי עותק לחברו, שדרן הרדיו קני אוורט, וביקש את חוות דעתו על השיר ושלא ישדר אותו. אוורט גילה התלהבות רבה מהשיר ושידר אותו ארבע עשרה פעמים בתוך יומיים, למרות הבקשה של מרקיורי. במהרה השיר הפך ללהיט המשודר ביותר בכל תחנות הרדיו. הלהקה אף יצרה סרט אמנותי שהוקלט לקידום השיר, מה שנחשב לאחד הקליפים הראשונים שיצאו בטלוויזיה על מנת לקדם סינגל. השיר התווסף לאלבום הרביעי של הלהקה, "A Night At The Opera", שזכה למעמד של "אלבום פלטינה" משולש בארצות הברית.
האלבום החדש אופיין בשילוב ייחודי בין מספר רב של סגנונות שהמשיך את המסורת של קודמו, כשמעל כולם בלט במיוחד השילוב בין מוזיקת רוק למוזיקה קלאסית. שאר הסגנונות כללו גם נגיעות במוזיקת קאנטרי בשיר "'39" ורוק כבד בשיר "I'm In Love with My Car". השיר הראשון באלבום, "Death On Two Legs" אופיין באגרסיות רבות, הן בלחנים והן במלל העוקצני, והוקדש לנורמן שפילד בעקבות יחסו ללהקה בזמן בו הייתה חתומה על החוזה עמו. הצלחת האלבום בבריטניה הובילה להצלחה עולמית והביאה את הלהקה למעמד של אחת הלהקות המצליחות ביותר בתקופה. האלבום נחשב לאלבום המצליח והמשובח ביותר של הלהקה בעיני רבים, ובשנת 2003 מגזין הרולינג סטון דרג אותו במקום ה-231 ברשימת "500 האלבומים הגדולים בכל הזמנים"". בעקבות הצלחת האלבום עלו גם המכירות של שלושת האלבומים הקודמים והם שבו לרשימות המצעדים וכל אחד מהם זכה במעמד של אלבום זהב.
כשיצא השיר "Bohemian Rhapsody" כסינגל, הוא זינק מיד לראש המצעדים בבריטניה ולמקום התשיעי בארצות הברית, ונכון ל-2008 הוא האלבום השלישי הנמכר ביותר בבריטניה. כמו כן הסינגל השני שיצא מהאלבום, "You're My Best Friend", שנכתב בידי ג'ון דיקון, הגיע למקום ה-16 במצעדים בארצות הברית.
בשנת 1976, לאחר שזכתה להכרה כלהקה מצליחה ומוערכת, ביצעה את אחת ההופעות המפורסמות ביותר שלה בהייד פארק, הופעה ללא תשלום אליה הגיעו כ-180,000 איש, הקהל הרב ביותר שפקד את הפארק עד אז. (לשם השוואה, אל מופע הלייב 8 שהתקיים ב-2005 הגיעו כ-150,000 איש).
בסוף אותה שנה יצא האלבום "A Day At The Races". כמו קודמו, האלבום נקרא על שם סרט של האחים מרקס ועטיפת האלבום הציגה גרסה נגטיבית של העטיפה מהאלבום הקודם. האלבום זכה להצלחה אדירה ולשבחים בקרב המעריצים והמבקרים כאחד והגיע לראש המצעדים בבריטניה. הלהיט שיצא מהאלבום, "Somebody to Love" (שנכתב בהשראת ארת'ה פרנקלין), כלל הכפלת קולות של מיי, טיילור ומרקיורי, מה שיצר מקהלת גוספל של מאה קולות וכאשר יצא כסינגל הוא הגיע למקום השני בבריטניה ולמקום ה-13 בארצות הברית. באותה תקופה, הצלחת הלהקה הייתה בקנה מידה עולמי, שיריה הושמעו בתחנות הרדיו ברחבי העולם ואף הביקורות העוקצניות של עיתוני המוזיקה על התדמית של הלהקה (ובמיוחד של מרקיורי) לא פגעו בהצלחתה.
בשנת 1977 יצא האלבום "News of the World". על אף שבתקופה בה יצא נמתחו עליו ביקורות רבות בעיתונות, עם חלוף הזמן האלבום זכה להכרה כאחד האלבומים המשפיעים ביותר על מוזיקת הרוק של סוף שנות השבעים, וכן כאחד המשפיעים ביותר על רוק האצטדיונים. שני שירים ממנו, "We Will Rock You" ו-"We Are the Champions", יצאו יחד כסינגלים שהפכו ללהיטים גדולים ואף הגיעו למקום הרביעי בארצות הברית, ובמהרה הגיעו למעמד של המנונים באירועי ספורט ובאצטדיונים.
באותה שנה, הוציא רוג'ר טיילור את פרויקט הסולו הראשון שלו בפורמט של סינגל. הצד הראשון היה גרסת כיסוי לשיר "I Wanna Testify" של הפרלמנטס, והצד השני היה שיר של טיילור, "Turn On The TV".
עם יציאת האלבום "Jazz" (ג'אז) ב-1978 התעוררה סערה תקשורתית גדולה בעקבות כרזה שיצאה לקידום מכירות האלבום במצורף אליו. בכרזה נראו עשרות נשים עירומות רוכבות על אופניים - המחזה שערורייתית של שני שירים מהאלבום "Bicycle Race" (מרוץ אופניים) ושיר בעל שם שערורייתי נוסף, "Fat Bottomed Girls" (בחורות עם ישבן שמן). עטיפת האלבום עוצבה בהשראת ציור על חומת ברלין שטיילור ראה במהלך סיור במקום.
האלבום זכה לביקורות לא מחמיאות וטענות כי עם כל שילוב הסגנונות שבאלבום, לא קיימת בו מוזיקת ג'אז כלל. הביקורות הבלתי מחמיאות נמשכו והשיא הגיע כשמגזין הרולינג סטון, ששיבח רבות את הלהקה בעבר, כתב: "לקווין אין את הדמיון המספיק כדי לנגן ג'אז, ובאותו עניין גם אין לה את הדמיון לנגן מוזיקת רוק בכלל...". כמו כן תגובות המעריצים היו צוננות והלהקה הפסיקה באופן זמני לעבוד על אלבומי אולפן.
למרות הכישלון היחסי, האלבום הניב להיט ענק אחד: Don't Stop Me Now.