17, 2003, Mullan was traded to the San Jose Earthquakes for a 2003 MLS SuperDraft second round pick. Mullan made his debut for the Earthquakes on March 16, getting the start in a 4–2 loss to C.S.D. Municipal in the CONCACAF Champions' Cup Round of 16. He would start the second leg as well, a 2–1 San Jose win, with Municipal advancing 5–4 on aggregate. On April 12, Mullan recorded an assist on Brian Ching's goal in the 1st minute to help the Earthquakes to a 2–1 win over the Colorado Rapids in San Jose's first game of the MLS season. In their next game, he scored his first goal for the Quakes to give San Jose a 1–1 draw with the Kansas City Wizards. Mullan enjoyed a productive first season playing as a wide midfielder, scoring 6 goals and adding 9 assists in the regular season, both career highs. He started all 30 regular season games as he helped the Earthquakes finish first in the Western Conference and second overall. In the first round of the playoffs, San Jose faced off with Mullan's former team, the Los Angeles Galaxy. After losing the first leg 2–0, San Jose returned home only to have the Galaxy take a 2–0 lead after 13 minutes, giving LA a 4-goal lead on aggregate. The Earthquakes rallied to score 5 goals and win in what is considered by some to be the greatest comeback in MLS history. and advance to the conference final where San Jose matched up with Kansas City. Mullan scored once as the Quakes beat the Wizards 3–2 to advance to MLS Cup. Mullan had one assist in the final as San Jose beat the Chicago Fire 4–2 to win MLS Cup 2003. The Earthquakes began the 2004 season on March 17, losing 3–0 to Alajuelense in the CONCACAF Champions' Cup. Mullan would score once in the return leg, but Alajuelense advanced 3–1 on aggregate. He scored his first league goal of the year on May 22 in a 4–2 win over the Galaxy. On August 7, Mullan had one goal and one assist as San Jose beat D.C. United 2–0, a performance that saw Mullan named MLS Player of the Week. Mullan enjoyed another productive regular season in 2004, playing 28 games (all starts) and recording 3 goals and 8 assists. The season was a disappointment for the Earthquakes, finishing 4th