בשלהי מלחמת העולם השנייה הגיע לארץ מר גריידל משקיע מאנגליה שחלומו היה להקים בארץ מלון, כדוגמת מלונות החוף בברייטון. ראש עירית תל-אביב דאז ישראל רוקח פעל להקצעת המגרש שהיה "מחוץ לעיר".
אבן הפינה ל"פלאזה הוטל" –שמו הראשון של המלון הונחה ב- 1950.
על מלאכת התכנון האדריכלי הופקד אדריכל ורנר יוסף ויטקובר שהתמחה בתכנון בתי המלון של אז כ"קטה דן" ו"גת רימון" ולימים תכנן גם את תכנית האב של אוניברסיטת תל אביב. בנית המלון נתמשכה זמן ממושך בעקבות סכסוך בין היזמים שאותו פתר טדי קולק (שהיה אז מנכ"ל משרד התיירות) על ידי שהביא לכניסת חברת "שרתון" הבינלאומית לתמונה.
ערב פסח 1961 נפתח המלון שהיה המפואר והחדיש מסוגו בארץ. ותארוהו העיתונים באותם ימים: "בנין מפואר מצופה אבן ירושלמית 206 חדרים עם שירותים מיוחדים," ציוד לטלפונים רדיו ומאור" טרקלינים ל- 4500 איש , בריכת שחיה וחדר אוכל ל- 700 איש."
לאור הצלחתו הרבה של המלון החליטו הבעלים להכפיל את שטחו ע"י בנית אגף נוסף הניצב לקודמו. התכנית נתקבלה בהתנגדות עזה הן ע"י דירי "מעונות עובדים" השכונה ממול והן ע"י אדריכלי המלון ויטקובר ובאומן שהתנגדו והגישו התפטרותם מהמשך התכנון. טענתם מוכרת: "חסימת הבריזה המערבית והפתיחה לים..."
האגף החדש נבנה ע"י אדריכל מבוסטון ויצר שעטנז של סגנונות.
לפני כ- 18 שנים נהרס מלון פאלאס, שרתון לשעבר, שצמח בחולות תל אביב לא הרחק משכונת מחלול. המלון היה נקודת ציון ולווה בצלליתו דור שלם מתושבי העיר, מרוחצי חוף שרתון ומבלייניו לשעבר של מועדון "מרבד הקסמים". ממועד הריסתו ועד היום האתר מגודר וסגור והינו פצע פתוח ברקמה העירונית. השאיפה ליצור כאן מפגש של העיר, שדרת נורדאו בואכה ימה לא מתממשת. כיום ובמחשבה שנייה, נדמה שעדיף היה לשמר את הבניין המקורי ולפתח סביבו את המפגש של שדרה, עיר, ים.