Chronologically, the first scene of Pulp Fiction is when we see Jules Winfield and Vincent Vegas driving on their way to a hit, the Royale with Cheese scene. They discuss beer in theaters, mayo on fries, and Royale with Cheese hamburgers. In this scene, they seem to have a real familiarity with each other.
But, they never say anything like "it's nice to meet you" or "your reputation precedes you" that would suggest that they did not know each other before this scene. They also never say anything like, "it's great to see you again" or "I didn't realize you had gone to Europe" that would suggest they did know each other before this scene.
Throughout the movie, they never discuss anything about how long their relationship has existed or how it might have started, but their manner suggests mutual respect and familiarity. They never discuss anything about a mutual past. They never discuss previous hits.
Is there any evidence that Jules and Vincent knew each other before the Royale with Cheese scene? Were they introduced immediately prior to this scene or have they worked together before or possibly done hits together before?