Persatuan Kebangsaan Melayu Tawau (PKMT) telah ditubuhkan pada tahun 1945-1949 di Tawau, Sabah. Persatuan ini diasaskan oleh beberapa orang pemimpin Melayu di Tawau pada masa tersebut iaitu selepas berakhirnya pendudukan Jepun di Sabah dan juga Tanah Melayu. Tujuan penubuhannya ialah untuk menyatukan seluruh bangsa Melayu di Tawau yang pada ketika itu telah sedar betapa pentingnya perpaduan di kalangan mereka untuk memastikan bangsa Melayu boleh bangkit memajukan diri mereka sama seperti bangsa lain walaupun dijajah oleh bangsa asing. Persatuan ini adalah kesinambungan daripada perjuangan pemimpin-pemimpin terdahulu yang cuba mempertahankan hak dan kepentingan orang-orang Melayu serta menjaga kedaulatan dan kemuliaan agama Islam khususnya untuk orang-orang Melayu Islam di Tawau. Ketika awal penubuhannya pada secara rasmi pada tahun 1949, ahli-ahli pertubuhan ini telah melantik Penghulu Abu Bakar menjadi pengerusi pertamanya sebagai menghormati beliau kerna beliau adalah pemimpin orang-orang Melayu di Tawau yang paling disayangi dan amat berjasa kepada orang Melayu pada ketika itu dan ketika zaman penaklukan tentera Jepun. Beliau memegang jawatan pengerusi sehingga beliau meninggal dunia pada tahun 1953 dan digantikan oleh anak didiknya yang juga menantu kepada abangnya iaitu Datuk Titingan Damsani atau lebih dikenali sebagai Abu Bakar Titingan. ( Nama 'Abu Bakar' diambil sempena nama mentor atau guru yang sangat beliau hormati iaitu nama Penghulu Abu Bakar sendiri ).[1]Masyarakat Melayu di Tawau pada ketika itu rata-ratanya adalah golongan miskin sama ada bekerja sebagai nelayan atau menanam tanaman dan hampir kesemuanya tidak berpelajaran tinggi. Kehadiran pemimpin-pemimpin Melayu yang agak terpelajar dan golongan peniaga kaya terutamanya Melayu yang berketurunan Arab telah membantu menyedarkan tanggungjawab masyarakat Melayu untuk bersatu di bawah satu pertubuhan. Dengan penyatuan ini juga masyarakat Melayu boleh berganding bahu bersama sama di dalam pelbagai aktiviti untuk merapatkan silaturahim dan perpaduan di kalangan mereka. Mereka juga boleh bantu membantu dan tolong menolong di dalam mengatasi pelbagai masalah yang dihadapi oleh masyarakat Melayu pada ketika itu. Bermula dengan tertubuhnya Persatuan Kebangsaan Melayu Tawau inilah kemudiannya mencetuskan Persatuan Islam Tawau ( PIT ) dan seterusnya bersama sama seluruh masyarakat Melayu Islam di seluruh negeri Sabah bergabung dan membentuk Pertubuhan Kebangsaan Sabah Bersatu (USNO) pada tahun 1961 yang berusaha mendapatkan kemerdekaan untuk negeri Sabah bersama Malaysia pada tahun 1963.