Kota Tuban memiliki asal usul dalam beberapa versi, pertama disebut sebagai Tuban dari lakuran watu tiban (batu yang jatuh dari langit), yaitu batu pusaka yang dibawa oleh sepasang burung dari Majapahit menuju Demak, dan ketika batu tersebut sampai di atas Kota Tuban, batu tersebut jatuh dan dinamakan Tuban. Saat ini wujud dari batu tersebut (watu tiban) masih ada dan dalam kondisi yang relatif utuh yang sekarang disimpan di Museum Kambang Putih, Tuban. Adapun versi yang kedua berupa lakuran dari metu banyu berarti keluar air, yaitu peristiwa ketika Raden Dandang Wacana (Kyai Gede Papringan) atau Bupati Tuban yang pertama membuka hutan Papringan dan anehnya, ketika pembukaan hutan tersebut keluar air yang sangat deras. Hal ini juga berkaitan dengan adanya sumur tua yang dangkal tetapi airnya melimpah, dan istimewanya sumur tersebut airnya tawar padahal berada di dekat pantai. Ada juga versi ketiga, Tuban berasal dari kata "tuba" atau racun yang artinya sama dengan nama kecamatan di Tuban yaitu Kecamatan Jenu.