Just have them start in the middle of a mission (escort, dungeon dive, whatever) with the descriptions of how they met and possibly-contrived reasons for working together just being swept under the rug as "assumed to have worked out one way or another".