Pempek telah adaberada di Palembang sejak masuknya perantau [[Tionghoa]] ke Palembang, yaitu di sekitar abad ke-16, saat [[Sultan Mahmud Badaruddin II]] berkuasa di kesultanan [[Palembang-Darussalam]]. Menurut tradisi, nama empek-empek atau pempek diyakini berasal dari sebutan ''apek'' atau ''pek-pek'', yaitu sebutan untuk paman atau lelaki tua Tionghoa.<ref name ="Kumparan-pempek">{{Cite web|title=Mengenal Asal-usul Pempek, Hidangan Populer dari Palembang |url=https://kumparan.com/kumparanfood/mengenal-asal-usul-pempek-hidangan-populer-dari-palembang-1548926055464103746|website=kumparan|language=id-ID|access-date=2020-09-22}}</ref>
Berdasarkan cerita rakyatmasyarakat, sekitar tahun 1617 seorang ''apek'' berusia 65 tahun yang tinggal di daerah Perakitan (tepian [[Sungai Musi]]) merasa prihatin menyaksikan tangkapan ikan yang berlimpah di Sungai Musi yang belum seluruhnya dimanfaatkan dengan baik, hanya sebatas digoreng dan dipindang. Ia kemudian mencoba alternatif pengolahan lain. Ia mencampur daging ikan giling dengan tepung tapioka, sehingga dihasilkan makanan baru. Makanan baru tersebut dijajakan oleh para apek dengan bersepeda keliling kota. Oleh karena penjualnya dipanggil dengan sebutan "pek … apek", maka makanan tersebut akhirnya dikenal sebagai empek-empek atau pempek.<ref name="KompasPempek">{{cite news|title = PEMPEK, Nilai Gizi "Kapal Selam" Paling Tinggi|publisher = Prof.Dr. Made Astawan, Kompas.com|date = 26 Maret 2004|url = http://www.kompas.com/kesehatan/news/0403/26/062251.htm|accessdate = 15 September 2007}}</ref>
Akan tetapi cerita rakyat ini patut ditelaah lebih lanjut, karena beberapa bagian kisah ini kurang tepat dengan kronologi sejarah. Misalnya, singkong sebagai bahan tepung tapioka baru diperkenalkan bangsa Portugis ke Indonesia pada abad ke-16, sementara bangsa Tionghoa telah menghuni Palembang sekurang-kurangnya sejak masa [[Sriwijaya]]. Selain itu ''velocipede'' (sepeda) baru dikenal di [[Perancis]] dan [[Jerman]] pada abad ke-18. Sultan Mahmud Badaruddin pun baru dilahirkan pada tahun 1767. Meskipun demikian, mungkin pempek merupakan adaptasi dari makanan olahan ikan Tionghoa; seperti bakso ikan, ''kekian'' atau pun ''ngohiang''.
