Dân số và đa dạng dân tộc từ quần đảo Indonesia với các sắc dân Dayak và Kutai là dân tộc bản địa sống ở vùng nông thôn. Các dân tộc lớn ở đây gồm người Java, người Hoa, Banjarese, Bugis và Malay, phần lớn sông ở các khu vực duyên hải.
Thời xa xưa, trên lãnh thổ Kalimantan Timur đã từng có một vương quốc cổ theo Ấn Độ giáo gọi là Kutai. Sự tồn tại của vương quốc này được khẳng định qua bằng chứng là một bia ký bằng đá gọi là Prasasti hiện được lưu giữ tại Bảo tàng Quốc gia Jarkarta. Bia ký này viết bằng tiếng Phạn và chữ cái Pallawa. Hiện có một bản sao của nó đặt tại trụ sở chính quyền tỉnh ở Samarinda.
Ngày 22 tháng 10 năm 2012, bốn huyện Malinau, Nunukan, Tana Tidung và Bulungan, cùng với thành phố Tarakan tách ra khỏi tỉnh Đông Kalimantan để thành lập tỉnh Bắc Kalimantan.