מיילר נולד בלונג בראנץ' בניו ג'רזי. שמו בלידתו היה מנחם ("נוחם", "נורמן") מלך מיילר. שמו השני, מלך, היווה את המקור לשם קינגסלי שאומץ עבורו (ונכתב כבר בתעודת הלידה). אביו, איזק ברנט מיילר, יליד ליטא שהיגר לארצות הברית מדרום אפריקה, היה מנהל חשבונות, אמו פאני לבית שניידר ניהלה סוכנות למטפלות. אביה שהיה בעל מכולת שימש כעין רב של הקהילה המקומית.
לאחר שחרורו מן הצבא, החל ללמוד באוניברסיטת הסורבון בפריז, עם מלגה מהצבא, ובשנת 1948 פרסם את ספרו הראשון "הערומים והמתים" המתבסס על ניסיונו כחייל. זהו רומן מלחמה ריאליסטי, המתאר בצורה חזקה ואלימה קבוצת חיילים אמריקנים הנלחמת לכיבושו של אי המוחזק בידי היפנים. ספר זה נחשב לאחד הספרים החשובים בסוגו, ולמייצג נאמן של הספרות שנכתבה על ידי דור הצעירים שלחם במלחמת העולם השנייה.
בשנים שלאחר מכן עבד מיילר כתסריטאי בהוליווד. חלק ניכר מעבודתו הספרותית לא התקבל על ידי המוציאים לאור. באמצע שנות החמישים התפרסם מיילר כמסאי המבקר את התרבות האמריקנית בת זמנו. ספרו "פרסומת לעצמי" (1959) המבוסס על קטעי יומן ורשימות, בוחן את האלימות, ההיסטריה, הפשע והבלבול בחברה האמריקנית, והיה בעל השפעה על דור הכותבים הצעירים בשנות השישים.
מיילר זכה פעמיים בפרס פוליצר. בפעם הראשונה על ספרו "צבאות הלילה" (1968), ובפעם השנייה על ספרו "שירת התליין" (1979). ספר זה, שהוא מפסגת יצירתו של מיילר, מתאר את הוצאתו להורג של הרוצח גארי גילמור. כן זכה מיילר במדליית אמרסון ת'ורו על מפעל חיים (1989), ושימש כנשיא הסניף האמריקאי של ארגון הסופרים PEN.
נטייתו של מיילר אל הפוליטיקה הובילה אותו לכתיבת ספרים כ"מדוע אנו בווייטנאם" (1967). בשנת 1969 התמודד על משרת ראש עיריית ניו יורק בתור "שמאלני שמרן" שצידד בהקמת מדינה נפרדת של העיר ניו יורק ונכשל. למרות היותו יהודי, מיילר לא היה אוהד ישראל, לא ביקר בה מעולם, והביע לא פעם תמיכה בפלסטינים.
מיילר הופיע כשחקן במספר סרטים, ביניהם סרטי אוונגרד של במאים "מחתרתיים" בשנות השישים. כן ביים מספר סרטים מסוג זה. כן ביים את הסרט "בחורים קשוחים אינם רוקדים", על פי ספרו. ספריו "העירומים והמתים", "חלום אמריקני" ו "שירת התליין" הוסרטו אף הם.
מיילר היה נשוי שש פעמים ואב לתשעה ילדים (לרבות בן חורג אחד), בהם הבמאי סטיבן מיילר, השחקנית קייט מיילר והעיתונאי (עורך המגזין "היי טיימס") ג'ון בפאלו מיילר. נפטר עקב אי-ספיקת כליות חריפה בבית החולים מאונט סיני במנהטן.
