אנדרה סולטנר החל את הקריירה שלו בגיל 15 באוטל די פארק, מילוז, באלזס מולדתו.
ב-1962 פתח אנדר סירמן את מסעדת "לטוס" (Lutèce) במנהטן, ניו יורק, הוא הביא את אנדרה סולטנר לכהן כשף המסעדה. מעט אחרי-כן סולטנר נכנס לשותפות עם סירמן והם ניהלו את המסעדה ביחד, עד ש- סירמן עזב אותה ופתח מסעדות במקומות אחרים. סולטנר נהיה השף-בעלים של "לטוס" עד שהוא מכר אותה ל- Ark Restaurants ב-1994. המסעדה נסגרה ב-14 בפברואר 2004, לאחר ירידה בהכנסות, זאת מכיוון שנטשו אותה לקוחות ותיקים, אחרי שאופיה ותפריטה השתנה בעקבות מכירתה ובעקבות פיגועי 11 בספטמבר, שגרם ללקוחות להוציא פחות כספים. למסעדה היה סניף בסטריפ של לאס וגאס. בזמן שסולטנר היה שף המסעדה זכתה לניקוד מקסימלי של ארבעה כוכבים מהניו יורק טיימס, היא ירדה לשלושה כוכבים תחת הבעלים החדשים.
בין התבשילים המפורסמים של מסעדת "לטוס" היו טארט בצל אלזסי וכבד אווזמוקפץ עם רוטב שוקולד כהה ומרמלדת תפוז מרה.
סולטנר החמיץ רק חמישה ימים מתוך 34 שנותיו ב"לטוס".
סולטנר חבר במספר ארגונים קולינריים בכללם המכון האמריקאי לאוכל וליין, שבו הוא ואשתו סימון הקימו את מלגת החינוך לאוכל על-שם אנדרה וסימון סולטנר, שנועדה לסייע לטבחים בתחילת דרכם. סולטנר הוא חבר הפדרציה הקולינרית האמריקאית, התאחדות השפים של אמריקה, וחברת הטבחים של צרפת. הוא שימש במשך למעלה מעשרים שנה כמאסטר שף של צרפת (Délegué Général of the Maîtres Cuisiniers de France) והוא יושב בחבר הנאמנים של חברת הנדבנות הקולינרית.
