The Tuti Tursilawati's execution without notification at the end of 2018 becomes one of the most important diplomatic and consular relations issues between Indonesia and Saudi Arabia. Indonesia was unable to seek for Saudi Arabia clarification because of the absence of bilateral agreement regarding consular notification between Indonesia and Saudi Arabia. Regarding the Vienna Convention on Diplomatic Relations 1961 and the Vienna Convention on Consular Relations 1963, the protection and assistance should both be provided by the Consulate to all their citizens abroad. By using normative legal research, the research aims to outline the importance of bilateral agreement on mandatory consular notification in dealing with a case of Tuti Tursilawati who was executed by Saudi Arabia government without any notification to the Republic of Indonesia government. The result shows that based on the Article 36 of the VCCR 1963, Mandatory Consular Notification should be delivered by Saudi Arabia before the execution. Making a bilateral agreement on Mandatory Consular Notification (MCN) with Saudi Arabia is very urgent to become a legal basis in helping and giving proper protection to the Indonesian who lives in Saudi Arabia in the future. Without that agreement, it will not be easy for Indonesia to access the information and giving assistance to protect the rights of the nationals from any cases happened abroad, especially related to criminal issues.