The English phrase ‘as soon as’ is made by attaching -자 (-ja) to plain verb base. However, the pattern is usually intensified in spoken language with addition of 마자. As such 가자 (kaja) or 가자 마자 (kaja maja) would mean the same ‘as soon as [someone] goes’.
Here is an example:
내가 학교에 도착하자마자, 바스가 떠났어요. (Naega hakyoe dochakhajamaja, basuga tteonaseoyo.) The bus left as soon as I arrived in School.
Note that even if the the second clause is past, the verb to which -자마자 is attached remains to be plain base. The verb at the end does the work to show it is past. Here is another example:
숙제를 마치자마자, 집에 돌아갔어요. (Sukjereul machijamaja, chipe dorakasseoyo.) She went back home as soon as she finished her homework.