"גבינה" היא מילה יחידאית בתנ"ך המופיעה בספר איוב: "הֲלֹא כֶחָלָב תַּתִּיכֵנִי וְכַגְּבִנָּה תַּקְפִּיאֵנִי". אך ככל הנראה הגבינה נזכרת גם בספר שמואל, בשם אחר, כאשר ישי אומר לבנו דוד לקחת את "חריצי החלב" מתנה לשר האלף.
מקורותיו המדויקים של ייצור הגבינה אינם ידועים, וההערכות נעות בין 8000 לפנה"ס (כשכבשים בויתו לראשונה) ועד 3000 לפנה"ס בערך. שבטים טורקיים במרכז אסיה או במזרח התיכון גילו את תהליך הייצור באותו זמן כשיוגורט הומצא. על פי אגדה ידועה, נווד ערבי שסחב חלב במכל עשוי מבטן בעל חיים במדבר גילה כי חלבו הופרד לגבנים ומי גבינה על ידי אנזים ההגבנה שבקיבת בעל החיים.
במציאות, ייצור גבינה פותח כשיטת שימור חלב מוחמץ או מוקרש דרך לחיצה או המלחה והשימוש באנזים הגבנה הגיע לאחר מכן. העדות הארכאולוגית הראשונה לייצור גבינה נתגלתה באתר פרהיסטורי בן 7,500 שנה בחבל קויאוויה שבפולין של ימינו. ארכאולוגים שעבדו באתר חשפו כלי חרס מחוררים, אשר לדעתם שימשו לסינון החלב בתהליך ייצור הגבינה אנליזה כימית של החרסים מצאה שומנים אופייניים לחלב מעלי גרה ואיששה את ההנחה. כיוון ששומנים מחלב גולמי אינם נשמרים, הרי שהחלב עבר תהליך עיבוד (לגבינה או גהי). גבינות קדומות אלו היו די מלוחות ומרות ודומות במראה לגבינות קוטג' ופטה של ימינו. ייצור גבינה אפשר ניצול חלב גם באוכלוסיות שבהן לא התפתחה עדיין עמידות ללקטוז.
מהמזרח התיכון יובא ייצור הגבינה לאירופה, שם אקלים קריר יותר קיצר את זמן ההמלחה. גבינה פחות חמוצה ומלוחה זו הייתה מקום ראוי להתרבות מגוון חיידקים ועובשים שמציעים טעמים חריפים יותר.