L’établissement des relations entre l’Algérie et l’Indonésie remonte à l’époque de la guerre d’indépendance que menée le peuple algérien contre le colonisateur français (1954-1962). Et en tant que président et fondateur du mouvement des pays non-alignés, et conformément à sa politique extérieur libre et efficace, l’Indonésie avait concrètement soutenue la lutte pour l’indépendance d’Algérie à travers la création d’un comité de soutien pour la libération de l’Algérie, du Maroc et de la Tunisie avec la participation des parties politiques membres aux parlement, présidé par le chef du gouvernement indonésien, Mohamed NACER, et M. Hamed ALKADIRI, membre de la commission des affaires étrangères au parlement indonésien, en tant que secrétaire général. En plus, le premier président de la république d’Indonésie, SOKARNO, envoyé des armes aux révolutionnaires algériens qui se trouvés aux frontières algéro-tunisiennes et avait invité les représentants algériens à assister en tant que observateurs au sommet Asie-Afrique de Bandung en 1955 et qui a été couronné par la déclaration de Bandung.

Entre 1956 et 1961, le Front de la Libération Nationale a ouvert une division de son bureau à Jakarta présidé par Lakhdar Ibrahimi afin de mobiliser la communauté internationale et avoir son appuie en particulier celle des pays membres du mouvement des non-alignés. Par ailleurs, l’islam comme religion et la politique extérieure récalcitrant la colonisation et ardemment soutenant l’indépendance des pays colonisés, sont des points communs qui ont contribué à la consolidation de relations exemplaires entre les deux pays. L’Indonésie fut aussi l’un des premiers pays à avoir reconnu l’indépendance de l’Algérie le 5 juillet 1962. L’année d’après, les deux pays ont ouvert des représentations diplomatiques pour officialiser l’établissement des relations diplomatiques. Par la suite, les relations se sont développées d’une façon permanente notamment en 1980. La coopération était concrétisée entre les deux pays dans divers domaines économique, commercial, social, culturel, mais aussi dans l’éducation et les affaires religieuses à travers l’échange d’étudiants.         

Ainsi, les relations historiques et exemplaires qui lient les deux pays sont devenues la base d’une coopération idéale sur les assemblées régionales et internationales. Les deux pays ont partagé des points de vues communes sur des questions internationales d’intérêts communs et aussi échangé l’appui de leurs candidatures pour des postes au sein d’organisations régionales et internationales comme La Conférence Islamique, le G15, le G77, le Mouvement des Non-alignés et les Nations Unies. Par ailleurs, le rythme des visites entre les officiels des deux pays c’est accéléré lorsque la Présidente de la République d’Indonésie, Mme MIGAWATI SUKARNO Putri, effectua une visite d’état en Algérie en 2002 et reçu une année après son homologue Algérien, M. Abdelaziz BOUTEFLIKA. Les deux visites on été couronnés par la signature de plusieurs accords de coopérations dans le domaine économique, commercial, social et culturel. En 2005, le Président Bouteflika a visité l’Indonésie pour la deuxième fois dans le cadre de sa participation à la commémoration du sommet Afro-Asiatique de Bandung 1955 et qui a été couronné par un document historique sur la coopération entre les deux continents appelé «New Asia Africa Strategic Partnership, NAASP» ou «La Nouvelle Coopération Stratégique Afro-Asiatique». L’Indonésie avait alors fortement apprécié la participation efficace du Président Bouteflika et avait exprimé son souhait d’avoir le soutien total de l’Algérie pour concrétiser la nouvelle coopération stratégique Afro-Asiatique.        

En 2003, les deux états ont formé une commission mixte au niveau de leurs ministères des affaires étrangères à la place de celle qui regroupé les hauts responsables et qui se réunissait depuis 2000. En effet, la commission s’est réunie en 2003 à Jakarta en présence de M. Abdelaziz BELKHADEM, Ministre des Affaires Etrangère à la tête de la délégation Algérienne et de son homologue M. Hassan WIRAYOUDA, à la tête de la délégation indonésienne. Les deux parties ont examiné les domaines de coopération possibles entre les deux pays notamment celui de l’économie, de la religion, de la communication, de l’éducation, de la culture, de la santé et de l’environnement. Les deux Ministres profitent aussi de leurs présences aux réunions internationales pour aborder des questions bilatérales comme se fut le cas en mois d’octobre à New York en marge de la réunion des Nations Unies et où les deux ministres se sont engagés à propulser les relations bilatérales.         

Les deux pays, qui avaient établi des relations commerciales dans les années 70, ont continué à travailler ensemble et au début des années 90, et grâce à sa croissance économique, l’Algérie a offert des occasions à l’Indonésie pour contribuer à cette croissance notamment à travers la réalisation des infrastructures. En effet, une société indonésienne participe actuellement à la construction de l’autoroute Est-West et espère prendre part, dans le future, aux grands projets d’infrastructures en Algérie.          
D’autre part, les relations exemplaires entre les parlements des deux pays représentent un facteur principal pour le rapprochement entre les deux peuples par le biais d’échange de visites et de délégations. En effet, en 2001, le Président du Conseil Consultatif Populaire de la République d’Indonésie, le Dr. Amine RAIS avait effectué une visite en Algérie et reçu le Président du Sénat Algérien, Abdelkader BENSALAH en 2002. De son coté, le président de l’Assemblé Populaire National s’est rendu pour la première fois en Indonésie pour participer au forum parlementaire Afro-Asiatique qui a eu lieu à Jakarta en 2006, et une deuxième fois en 2007 pour prendre part à un assemblé général de l’Union Parlementaire International à Bali où les parlements des deux pays ont réitéré leur volonté de renforcer la coopération entre les deux peuples par le bais d’une commission d’amitié parlementaire.