Rencana pembangunan hotel sebagai bagian dari perluasan [[Tunjungan Plaza]] III sudah direncanakandibahas sejak tahun 1993. Awalnya, Pakuwon Jati hendak membangun dua hotel: satu hotel berbintang 4 dengan 313 kamar dan satu hotel berbintang 5 dengan 320 kamar. Pada akhirnya, hanya proyek kedua saja yang terlaksana, sementara proyek pertama diganti dengan apartemen.<ref name="SGPC">{{cite web |url=https://setiapgedung.id/2020/04/tunjungan-plaza.html |title=Tunjungan Plaza |website=Setiap Gedung Punya Cerita |date= 17 April 2020 |access-date=13 Agustus 2024}}</ref>
Hotel mulai dibangun pada bulan Oktober 1993 dan selesai pada akhir tahun 1995. Rancangan bangunan hotel yang berciri khas [[pascamodernisme]] digarap sendiri oleh Pakuwon Jati melalui biro arsitek Pakuwon Jati Design Group. Biaya yang dikeluarkan untuk membangun hotel dilansir sebesar Rp 175Rp175 miliar. Pakuwon Jati menekan kontrak dengan [[Hotel Sheraton|ITT Sheraton]] untuk mengelola hotel yang diresmikan dengan nama Sheraton Surabaya Hotel & Towers pada tanggal 5 Januari 1996 oleh [[Kementerian Pariwisata dan Ekonomi Kreatif Republik Indonesia|Menteri Pariwisata, Pos, dan Telekomunikasi]] [[Joop Ave]].<ref name="SGPC" /> Hal ini menandakan awal kerja sama kedua perusahaan tersebut, kerja sama yang masih berjalan hingga sekarang; [[Marriott International]], pemilik Sheraton saat ini, mengelola hotel-hotel yang berdampingan dengan [[Pakuwon Mall Surabaya]],<ref>{{cite web |url=https://properti.kompas.com/read/2019/12/08/195203721/pakuwon-resmikan-hotel-four-points-kedua-di-surabaya |title=Pakuwon Resmikan Hotel Four Points Kedua di Surabaya |website=Kompas |date=8 Desember 2019 |access-date=13 Agustus 2024}}</ref> [[Pakuwon Mall Jogja]],<ref>{{cite web |url=https://travel.kompas.com/read/2018/03/09/220000727/hotel-bintang-lima-marriott-kini-hadir-di-yogyakarta |title=Hotel Bintang Lima Marriott Kini Hadir di Yogyakarta |website=Kompas |date=9 Maret 2018 |access-date=13 Agustus 2024}}</ref> dan [[Gandaria City]].<ref>{{cite web |url=https://money.kompas.com/read/2015/11/09/170900527/NaN |title=Hotel Sheraton Kedua di Jakarta Siap Menerima Tamu |website=Kompas |date=9 November 2015 |access-date=13 Agustus 2024}}</ref>
Pada tanggal 20 Juni 2016, Pakuwon Jati meresmikan [[Four Points by Sheraton]] Surabaya, Tunjungan Plaza, sebagai bagian dari perluasan Tunjungan Plaza V. Hotel ini sama-sama dikelola oleh Marriott International, namun menetapkan tarif yang lebih rendah dibandingkan dengan Sheraton Surabaya Hotel & Towers.<ref>{{cite journal |last1=Tiffany |first1=Tiffany |last2=Goenawan |first2=Felicia |last3=Monica |first3=Vita |date=2019 |title=Brand Awareness Masyarakat Surabaya Terhadap Four Points by Sheraton Surabaya |url=https://publication.petra.ac.id/index.php/ilmu-komunikasi/article/view/10092 |journal=Jurnal E-Komunikasi |volume=7 |issue=2 |pages= |doi= |access-date=13 Agustus 2024}}</ref>
