โอตารุเคยเป็นถิ่นที่อยู่ของชาวไอนุ และเชื่อกันว่าชื่อ"โอตารุ"มีที่มาจากภาษาไอนุ ซึ่งอาจหมายถึง "แม่น้ำที่ไหลผ่านหาดทราย" ถ้ำเทะมิยะซึ่งหลงเหลืออยู่เพียงเล็กน้อยในปัจจุบันมีภาพเขียนผนังถ้ำตั้งแต่ยุคโซกุ-โจมง หรือประมาณ พ.ศ. 943(400) ต่อมาเมื่อ พ.ศ. 2408(1865) รัฐบาลเอะโดะได้ยกสถานะโอตารุเป็นหมู่บ้าน และเมื่อ พ.ศ. 2423 ทางรถไฟสายแรกในฮกไกโดได้เปิดให้บริการวันละเที่ยวระหว่างโอตารุกับซัปโปะโระ ต่อมาเมื่อวันที่ 1 สิงหาคม พ.ศ. 2465(1922) โอตารุได้รับการยกสถานะให้เป็นเมือง