Pada tahun 1923 terdirinya sebuah sekolah perempuan dengan nama Sekolah Perempuan Ngee Heng. Nama tersebut diambil sempena nama kampung Ngee Heng yang menjadi lokasi sekolah ini.
Bangunan setingkat telah didirikan di atas padang
Pengasas sekolah ini diasaskan oleh Pn Hjh Zaiton bt Sulaiman yang lebih dikenali sebagai Ibu Zain. Beliau merupakan penyelia sekolah-sekolah perempuan Melayu dan agama Negeri Johor pada masa itu. Hasil pemikiran Ibu Zain, sekolah ini ditukar nama menjadi Sekolah Melayu Perempuan Bandar Tinggi. Tujuannya untuk menaikkan semangat orang Melayu dan meningkatkan pelajaran untuk anak-anak perempuan itu. Idea ini telah disambut baik oleh Penguasa Pelajaran HJ Che sman.
Sebaik sahaja sekolah dibuka pada tahun 1971 terdapat lebih 300 orang murid. Aliran darjah yang mula dijalankan adalah bermula darjah 0(not) dan diikuti darjah 1 hingga 6. Guru Besar yang pertama bertugas disekolah ini ialah Pn Hjh Salmah bt Hj Ahmad (1931- 1941).
Pada tahun 1930, pakaian seragam murid-murid diperkenalkan. Bagi murid darjah 0(not) hingga darjah tiga ditetapkan memakai blaus pendek putih dan berkain kembang, berkasut putih serta bertudung kepala. Guru-gurunya pula memakai baju kurung putih, berkain batik dan bertudung kepala. Sanggul tinggi dan sanggul dua merupakan fesyen yang diminati pada masa itu. Identiti guru-guru yang mengajar di sini sangat dikenali khususnya sekolah sekitar daerah Johor Bahru.
ZAMAN PERANG DUNIA KEDUA
Pada masa tercetusnya perang dunia kedua aitu 2 Februari 1942, sekolah ini ditutup buat sementara dan dijadikan pusat perlindungan mangsa-mangsa perang yang datang dari Mersing dan Endau. Selain itu, turut dijadikan juga pusat pentadbiran tentera Jepun.
ZAMAN SELEPAS PERANG HINGGA KINI
Apabila perang telah reda, barulah sekolah ini dibuka semula pada tahun 1944. Guru Besar yang bertugas pada masa itu ialah Hjh.Maimunah bt.Hj.Abd.Rahman. Pada tahun 1947, bangunan lama yang terletak di atas padang yang digunakan oleh murid-murid lelaki yang kemudiannya ditempatkan bagi murid-murid Pra sekolah hingga ke darjah 4. Dengan bertambahnya murid pada 1972, bangunan baru dua tingkat telah didirikan di bahagian bawah pada tahun 1974. Bangunan ini dibina di atas tapak dua buah rumah guru dan dijadikan padang permainan seperti yang ada sekarang.
SENARAI NAMA GURU BESAR SK (P) BANDAR TINGGI
| Bil. | Nama | Tahun berkhidmat |
| 1. | Pn.Hjh.Maimunah binti Hj A. Rahman | 1941-1955 |
| 2. | Pn.Hjh.Khadijah binti Hj. Bakri | 1955-1965 |
| 3. | Pn.Hjh.Habsah binti Hj. Ahmad | 1966-1976 |
| 4. | YM.Tengku Esah binti Abu Bakar | 1977-1981 |
| 5. | Pn.Kalsom binti Rouse | 1982-1985 |
| 6. | Cik Zalaha binti Mahmud | 1985-1986 |
| 7. | Pn.Hjh.Khadijah binti Mohd Noor | 1987-1992 |
| 8. | Pn.Hjh.Zahrah binti Omar | 1992-1993 |
| 9. | Pn.Hjh.Tashahbinti Ahmad | 1994-1996 |
| 10. | Pn.Latifah binti Mohd Taib | 1996-1998 |
| 11. | Pn.Hjh.Halimah binti Ismail | 1.4.1998-9.10.2000 |
| 12. | Pn.Hjh.Azizah binti Ahamad Tan | 10.10.2000-16.8.2001 |
| 13. | Pn.Yos Fatimah binti Selamat | 17.8.2001-30.9.2003 |
| 14. | Pn.Hjh.Siti Latifah binti Hj.Adnan | 1.10.2003-31.5.2004 |
| 15. | Pn.Hjh.Puziah binti Zakariah | 1.6.2004-30.9.2005 |
| 16. | Pn.Ainon binti Abd. Ghani | 1.10.2005-28.12.2007 |
| 17. | Pn.Hjh.Sanipah binti Ali | 29.12.2007-sekarang |
BILANGAN PELAJAR SEKOLAH
| Bil. | Tahun | Bil.Murid | Bil.Kelas |
| 1. | 2009 | 27 | 3 |
| 2. | 2008 | 18 | 3 |
| 3. | 2007 | 17 | 3 |
| 4. | 2006 | 24 | 3 |
| 5. | 2005 | 31 | 4 |
| 6. | 2004 | 31 | 4 |
| 7. | 2003 | 28 | 3 |
| 8. | 2002 | 26 | 3 |
| 9. | 2001 | 23 | 3 |
| 10. | 2000 | 23 | 3 |
| 11. | 1999 | 16 | 3 |
JUMLAH KESELURUHAN PELAJAR PADA TAHUN 2010
| KESELURUHAN | MELAYU | CINA | INDIA | LAIN-LAIN | JUMLAH BESAR |
| 84 | 6 | 15 | 78 | 183 |
BILANGAN PELAJAR TAHUN 2010
| TAHUN |
MELAYU
| CINA | INDIA | LAIN-LAIN | JUMLAH | JUMLAH BESAR |
| 1Z | 7 | - | - | 6 | 13 | 13 |
| 2Z | 5 | - | 3 | 2 | 10 | 10 |
| 3Z | 5 | - | 1 | 4 | 10 | 10 |
| 4Z | 5 | - | 1 | 4 | 10 | 10 |
| 5Z | 8 | 1 | 5 | 3 | 16 | 17 |
| 6Z | 3 | - | 1 | 3 | 7 | 7 |
| JUMLAH | 33 | 1 | 11 | 22 | 67 | 67 |
BILANGAN PELAJAR PENDIDIKAN KHAS DAN PRASEKOLAH 2010
| KELAS P.KHAS | MELAYU | CINA | INDIA | LAIN-LAIN | JUMLAH BESAR |
| PRA (KHAS) | 2 | - | - | - | 2 |
| KHAS A | 6 | 2 | - | 3 | 10 |
| KHAS B | 9 | - | - | - | 9 |
| KHAS C | 7 | - | - | - | 7 |
| KHAS D | 5 | - | 1 | - | 6 |
| KHAS J | 5 | - | 1 | - | 6 |
| JUMLAH | 34 | 2 | 2 | 3 | 41 |
| PRA SEKOLAH | 17 | 1 | - | 5 | 23 |
| JUM.PRA & KHAS | 51 | 5 | 4 | 11 | 71 |
SK (P) Bandar Tinggi ingin menjadi Sekolah Unggul
Penjana Generasi Terbilang
Sek Bandar Tinggi nama diberi
Sekolah yang kami cintai
Dalam bandar megah berdiri
Lambang Kemegahan Pertiwi
Pelajaran cahaya Kebahgiaan
Nama Sekolah Itulah Cogan
Amalkanlah Wahai kawan-kawan
Ilmu Pengetahuan Punca Kebahgian
Jasa Bakti Sekolah Kami
Tak Dapat di nilai di beli
Ramai Menjadi Pemimpin Negeri
Tak Kurang Ibu Terpuji
