אליקים רובינשטיין השלים תואר בשפה וספרות ערבית ובלשון עברית ב-1967, ושנתיים מאוחר יותר השלים תואר ראשון במשפטים. לאחר שחרורו מצה"ל ב-1970 השתלב במחלקה המשפטית של משרד הביטחון, וב-1974 מונה ליועצו האישי של שר הביטחון משה דיין. ב-1977 עבר למשרד החוץ, וכיהן בו בשורה של תפקידים, ביניהם סמנכ"ל לעניני ישום חוזה השלום עם מצרים, חבר משלחת ישראל לקמפ-דיוויד וסמנכ"ל משרד החוץ במינוי אישי של שגריר. כמו כן כיהן כיועץ לשר החוץ.
ב-1985 מונה רובינשטיין לציר בשגרירות ישראל בוושינגטון. בנובמבר 1986 שב לישראל למינוי מזכיר הממשלה. במהלך כהונתו מילא מינויים בוועידות דיפלומטיות ומשפטיות רבות, ביניהן כיו"ר צוות המשא ומתן על מיזכר ההסכמה בין ישראל לארה"ב, המסדיר את יחסי שתי המדינות; חבר משלחת ישראל לוועידת מדריד ויו"ר משלחת ישראל למשא ומתן עם ירדן.
ב-1992 מונה רובינשטיין למשנה ליועץ המשפטי לממשלה. ב-1994 מונה ליועץ המשפטי למערכת הביטחון. ביולי 1995 מונה לשופט בבית המשפט המחוזי בירושלים.
בפברואר 1997 מונה ליועץ המשפטי לממשלה. בכהונתו נאלץ להתמודד עם ביקורת רבה על הגשת או גניזת כתבי אישום רבים נגד אישי ציבור, בהם בנימין נתניהו, עובדיה יוסף, עזר ויצמן ויצחק מרדכי.
רובינשטיין נשוי ואב לארבעה.