Jurusan Teknik Mesin dan Program Studi D3 Teknik Mesin Alat Berat didirikan secara bersamaan pada tahun 2002 melalui jin Operasional Dirjenidikti dengan SK No 68/D/O/2002 dibawah Yayasan Pendidikan Pemerintah Kota Balikpapan.
Dalam upaya meningkatkan mutu lulusan, pada tahun 2003 Program Sudi Teknik Mesin Alat Berat dikerjasamakan dengan Central Queensland Institute of TAFE Australia. Hasilnya lulusan angkatan pertama, disamping mereka menerima Ijazah Diploma III dari Politeknik Balikpapan juga mendapatkan Certificate IV Earth & Heavy Vehicle Maintenance dari Central Queensland Institute of TAFE Australia.
Pada tahun 2011 Politeknik Balikpapan berubah status menjadi Negeri. Melalui Surat Keputusan Menteri Pendidikan Nasional No. 41 tahun 2011 tentang Pendirian, Organisasi, Dan Tata Kerja Politeknik Negeri Balikpapan. Dengan demikian Program Studi D3 Teknik Mesin Alat Berat yang semula dibawah manajemen Yayasan Pemerintah Kota Balikpapan berubah menjadi dibawah Kementerian Pendidikan Nasional yang selanjutnya pada tahun 2015 berubah dibawah Kementerian Reset Teknologi dan Pendidikan Tinggi, dan terakhir pada tahun 2019 berubah kembali dibawah Kementerian Pendidikan dan Kebudayaan.
Akreditasi Program Studi D3 pada awal didirikan adalah “B”. selanjutnya pada tahun 2014 dilakukan re-akreditasi dan konsisten dengan predikat “B” hingga saat ini.