The treaty allows either country to demand extradition for convicted criminals or suspects and while not directly aimed at Kalejs, according to Latvian legal authorities, it is Latvia's most decisive move so far to resolve a case that has brought international attention to war crimes committed during the Nazi occupation.
Even with it in place, however, authorities in Latvia are still hesitant to say when Kalejs might be charged.
An attorney from Latvia's prosecutor's office has spent the last two weeks in Moscow pouring over government files related to Nazi war crimes that the prosecutor's office says could be critical in charging the 86-year-old Kalejs.
The attorney returned with more than 700 documents, according to the prosecutor's office.
"We have to be very cautious to evaluate all the material that might come through the mutual assistance that's going on at the moment in Russia," said Rudite Abolina, the prosecutor in charge of the Kalejs investigation. "These cases should be investigated very carefully and we should proceed only from the facts not from emotions."
Latvia has also launched an investigation into suspected Nazi war criminal, Karlis Ozols, who also lives in Australia.
Abolina would not comment on when her office might charge Kalejs or Ozols and that silence has troubled Nazi-hunting organizations like the Simon Wiesenthal Center.
"We welcome the signing but unless it is applied to Kalejs and Ozols it will be irrelevant," said Efraim Zuroff, head of the center's Jerusalem office. "The bottom line is that Latvia should think of the whole [case] as a challenge and a history lesson, not as an attack on Latvian patriots."
Kalejs has admitted being a member of the Arajs Commando, a Nazi-backed regiment responsible for killing as many as 30,000 Jews during World War II. But he has denied involvement in any war crimes.
Kalejs fled to Australia in January after Great Britain threatened to deport him as a suspected Nazi war criminal. He now resides in Melbourne and is consulting an attorney, according to the prosecutor's office here.
Parliaments in both countries must approve the treaty before it takes effect, a process that both sides say should move quickly.
The Australian government passed special regulations earlier this month to allow for the possible extradition of Kalejs should Latvia charge him.
"If a request were to be made between now and the treaty's ratification that request can be acted upon," said Stephen Brady, Australia's ambassador to Sweden and the Baltics, who was in Riga for the treaty signing.
However, a request for extradition could face delays in the Australian legal system if Kalejs lodges an appeal.